The computation requirements for mapping and sequencing the human genome might soon exceed the capability of any existing supercomputer. The systolic array processor presented in this paper, called biological information signal processor (BISP), has the capability to satisfy the current and anticipated future computational requirements for performing sequence comparisons based on the T.F. Smith and M.S. Waterman algorithm (1981) as extended by M.S. Waterman and M. Eggert (1987). The BISP can conduct the most time consuming sequence comparison functions, establishing both global and local relationships between two sequences. A modified Smith and Waterman algorithm is presented in this paper for efficient VLSI implementation. Methods are developed to reduce the BISP systolic array I/O bandwidth problem by reporting only the statistical significant results. Estimated performance of the BISP is compared with several different computer architectures.>

The Biological Information Signal Processing (BISP) is a system for high speed sequence comparisons designed to support the computation requirements for mapping and sequencing the human and other genomes. The heart of a BISP system is a versatile processor chip that can conduct the most time consuming sequence comparison functions, establishing both global and local relationships between two DNA or protein sequences. Because of \nthe application’s strong computation and communication \nrequirements, a programmable systolic array architecture was \ndeveloped. A BISP system can include a large number of \nprocessing elements; the initial BISP demonstration system \nconsists of 768 BISP elements, capable of delivering more than 6.25 x 10^9 integer operations per second. The system can be expanded to include over 4,000 elements, This paper describes the comparison algorithm and outlines the BISP chip and system designs. Estimated performance of the BISP system is compared with several different computer architectures.

The performance of a message-passing multiple instruction multiple data (MIMD) concurrent computer depends in large part on the communication processing overhead. A high-speed communication architecture is proposed for a hypercube-type supercomputer to attain the specific goals of message-driven processing. These goals include: direct hardware execution of messages, queueing of messages (using various paradigms), adaptive message routing, and special local registers for fast context switching. A hyperswitch network capable of high-speed switching is used to perform message routing. Available communication paths are pruned by the routing algorithm in response to congestion within the network to evaluate the best-first available path between any two nodes. Simulation results show that this architecture reduces message reception latency by two to three orders of magnitude when compared to commercial hypercube systems. This communication architecture extends the application of parallel systems to supercomputer problems that place heavy demand on the communication network for high bandwidth, low latency, and non-local communication. Detailed simulation studies for the proposed communication architecture are presented.

A method is presented that realizes a kind of interconnection network, called a hyperswitch network, that is achieved using a mixture of static and dynamic topologies. Available of fault-free paths need not be specified by a source because the routing header can be modified in response to congestion or faults encountered as a path is established. This method can be accomplished in a static topology such as the hypercube network if the nodes have switching elements which are capable of dynamically performing the necessary routing header revisions. Detailed simulation results show that the hyperswitch network is consistently more efficient than fixed-path routing for large message traffic conditions. The simulation results also show that the hyperswitch network has equivalent latency overhead for messages with localized and antilocal destinations (i.e., less than a 25% difference between diameter 1 and 5).>