The growing sophistication in radiation treatment strategies requires the utilization of increasingly accurate, but computationally intense, dose algorithms, such as the electron pencil-beam redefinition algorithm (PBRA). The sequential implementation of the PBRA is in production use at the MD Anderson Cancer center. The PBRA is difficult to parallelize because of the large amounts of data involved that is accessed in an irregular pattern taking varying amounts of time in each iteration. A case study of the parallelization of the PBRA code on a Beowulf cluster using PVM and PThreads is presented. The solution uses a non-trivial way of exchanging minimal amount of data between processes to allow a natural partitioning to work. Multi-threading is used to cut down on the communication times between CPUs in the same box. Finally, an adaptive load-balancing technique is used to further improve the speedup.