Finding Test-and-Treatment Procedures Using Parallel Computation.
Abstract
A parallel algorithm for the NP-hard problem test-and-treatment is presented for a machine whose number of connections is 3p(2 squared), where p is the number of processing elements (PEs), and where the PEs are simple enough such that a machine with 2 to the 20th power PEs is currently implementable and to the 30th power PE machine is feasible. The speedup of O (sub p (log p) is realizable because we are able to transform the dynamic programming solution into the ASCEND/DESCEND scheme with considerable attention to the communication problem. This algorithm is realized on the Boolean Vector Machine, a fully designed cube-connected-cycle system where processor allocation and other control issues have been faced. The particular NP-hard problem is of independent interest; it generalizes the binary testing problem by introducing treatments on an equal basis with tests. Applications of this test-and-treatment problem are found in medical diagnosis, systematic biology, machine fault location, laboratory analysis and many other fields. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1985
- Accession Number
- ADA162141
Entities
People
- D. W. Loveland
- L. D. Duval
- R. A. Wagner
- Yunghsiang S. Han
Organizations
- Duke University