Accession Number : ADA190678

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

Descriptive Note : Master's thesis,

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING

Personal Author(s) : Carpenter, Barry A

PDF Url : ADA190678

Report Date : Dec 1987

Pagination or Media Count : 165

Abstract : 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.

Descriptors :   *PARALLEL PROCESSING, *ALGORITHMS, *ANTIMISSILE DEFENSE SYSTEMS, ALLOCATIONS, BATTLES, CONTROL, COSTS, HEURISTIC METHODS, MANAGEMENT, NODES, PERFORMANCE TESTS, THESES, WEAPONS, EXPERIMENTAL DATA

Subject Categories : Computer Systems
      Antimissile Defense Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE