Implementation and Performance Analysis of Parallel Assignment Algorithms on a Hypercube Computer

摘要

The process of effectively coordinating and controlling resources during a military engagement is known as Battle Management/ Command, Control, and Communications (BM/C3). One key task of BM/C3 is allocating weapons to destroy targets. The focus of this research is on developing parallel methods to achieve fast and cost effective assignment of weapons to targets. Using the sequential Hungarian method for solving the assignment problem as a basis, this report presents the development and relative performance comparison of four parallel assignment algorithms implemented on the Intel iPSC hypercube computer. The first approach partitions the problem space into smaller, independent subproblems and assigns each to a processing node in the hypercube. The second and third approaches also partition the problem space, but they assign each partition to a group of processing nodes. Each group is controlled by a separate node which further subdivides the partition among members of the group. In the second approach, the control node acts as an arbitrator to eliminate the redundant assignment of weapons to targets by idling redundantly allocated weapons. The third approach eliminates redundant weapon allocations by selecting the least costly redundant allocations and directing additional processing to reallocate the more costly weapons. The fourth approach is a parallel implementation of the Hungarian algorithm, where certain subtasks are performed in parallel. This approach produces an optimal assignment instead of the sub-optimal assignment generally obtained using either of the three heuristic approaches.