SWASAD Smith & Waterman-algorithm-specific ASIC design

Han, Tony. (2002). SWASAD Smith & Waterman-algorithm-specific ASIC design MPhil Thesis, School of Computer Science and Electrical Engineering, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
THE16391.pdf Full text application/pdf 17.55MB 2
Author Han, Tony.
Thesis Title SWASAD Smith & Waterman-algorithm-specific ASIC design
School, Centre or Institute School of Computer Science and Electrical Engineering
Institution The University of Queensland
Publication date 2002
Thesis type MPhil Thesis
Supervisor Downs, T.
Total pages 233
Collection year 2002
Language eng
Subjects L
290902 Integrated Circuits
700199 Computer software and services not elsewhere classified
Formatted abstract
In recent times, large, government-sponsored scientific projects such as the Human Genome Project in the United States have contributed to a massive increase in the quantity of data regarding proteins, DNA, and RNA. The Smith and Waterman (S&W) algorithm is one of the fundamental methods of analysing and searching the large amounts of data now available. However, an alignment algorithm such as this constitutes a large computational load which leads to a performance bottleneck on CPU-based computers and servers.

This thesis presents the Smith and Waterman Algorithm-Specific ASIC Design (SWASAD) project. This is a hardware solution that implements the S&W algorithm and provides better performance in comparison with software-based solutions implemented on computers or servers. The main S&W calculations are performed on the SWASAD chips, which are implemented using high-speed Application-Specific Integrated Circuits (ASIC). The SWASAD chips execute the S&W algorithm faster than similar existing hardware products, and involve a lower engineering design cost than these products.

The SWASAD is an improvement of the Biological Information Signal Processor (BISP) design. Various associated algorithms, and the software or hardware implementations of these algorithms, are reviewed initially in this thesis. Following this, the target specifications for the SWASAD are defined, with the general objective of the project being to achieve a number of improvements over the BISP and other bioinformatics database searching hardware.

Finally, the performance and specifications of the SWASAD are compared with those of existing products reviewed in the thesis, in order to highlight the SWASAD's improvements. The SWASAD chip fabricated under a 0.5 µm process achieves a high clock speed of 50 MHz, with a large calculation amount of 3200 million Matrix Cells Per Second (MCPS) per chip, for a layout size of 7.1 mm by 7.1 mm. A Kestrel chip with a layout size of 7.2 mm by 8.3 mm, and a similar architecture, application and fabrication process to the SWASAD, operates at 20 MHz with only 1280 million MCPS per chip. In comparison, the BISP operates at 12.5 MHz clock speed and has only 200 million MCPS, for a layout size of 10 mm x 11 mm. The SWASAD contains 64 PEs per chip, rather than the 16 PEs per chip of the BISP, and the SWASAD's data bus bandwidth requirement is smaller than the BISP's. This reduction in bandwidth is attained by using the distance S&W algorithm rather than the similarity S&W algorithm used by the BISP.

The author concludes by suggesting future work that could be done in relation to the SWASAD, and by affirming that the SWASAD project achieves its target specifications. The SWASAD hardware was not physically built for a hardware demonstration, as the deadline for chip fabrication was not met. However, various design simulations and verifications prove the SWASAD's functionality and manufacturability.
Keyword Genetic code

Document type: Thesis
Collection: UQ Theses (RHD) - UQ staff and students only
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 24 Aug 2007, 17:53:28 EST