Personally - I would be VERY wary of trying to retrofit threading. There are many big scary bugs that are lurking within to bite you. I would strongly recommend that you assume you'll need a rewrite from scratch, and then borrow from your original source.
It at least looks like you're dealing with an implicitly parallel problem, so I would suggest:
- Redraft your code such that you have a 'worker' subroutine, which handles one thing at a time. (Multiple are OK, if you've different cases to handle and you want to parallelise)
- Use Thread::Queue, and 'feed' your worker with a queue. (unthreaded).
- Consider your 'worker' sub as a thread, and spawn multiple
Here's a really basic template for what I mean: A basic 'worker' threading example.
(Not to denigrate the perfectly sound advice other Monks have offered. This is purely my opinion as to how I would approach your problem)