The answer to both questions is: it depends upon the program. Some programs lend themselves to multi-threading and the conversion can be quite simple. Others, even quite simple programs, can be very hard.

There really is no way to tell you whether it will be easy or hard without at least a fairly detailed high level description of the program. Even then, even if that high level description suggests that the problem could lend itself to threading reasonably easily, whether it does or not, will depend a lot upon how you have coded your program to solve that problem.

Also, threading isn't the only option possible. Running multiple copies of the program on different subsets of the total dataset may be a simpler option.

In the end, the best way to advise you would be to see the code. (Don't take that as an invitation to post thousands of lines of code here!). A high level description of the program and it dataflows would be a good starting point.