Accession Number:

ADA162141

Title:

Finding Test-and-Treatment Procedures Using Parallel Computation.

Descriptive Note:

Technical paper,

Corporate Author:

DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE

Report Date:

1985-10-01

Pagination or Media Count:

27.0

Abstract:

A parallel algorithm for the NP-hard problem test-and-treatment is presented for a machine whose number of connections is 3p2 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 ASCENDDESCEND 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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE