The first thing would be to find where your program spends the most time, and look to see if that can be improved. You might look at the Devel::* modules, such as Devel::DProf, to help with this portion of the process.

You might also wish to consult several of the excellent books available. Some of the books I am aware of (and own) that might be helpful include Programming Perl, Advanced Perl Programming, Mastering Algorithms with Perl, and Perl Cookbook.