THE DERIVATION OF A HIGH SPEED SIEVE DEVICE

Abstract

Sieving is a technique used in computational number theory for solving systems of simultaneous linear congruences. The technique is efficient in the sense that it avoids the use of expensive operations, and may be implemented directly in hardware. A variety of sieve applications are discussed and categorized, the intrinsic difficulty of sieve problems is analyzed, and previous special-purpose sieve devices are surveyed. Next, a sieve device model is developed. Based on the limited hardware resources available in the chosen integrated circuit technology, selections are made from an assortment of algorithms, timing methodologies, and module implementations. The abstract structure of the sieve model is formally defined, and many of the internal optimizations are formally validated. Finally, a VLSI implementation of the sieve model is presented. This is the first single chip sieve. It worked the first time it was fabricated, and over 90 of the die have been packaged and successfully tested. Although this single device is the fastest known dedicated system for solving an important class of sieve problems, a powerful optimization is developed that exploits multiple sieve chips. The use of a reasonably small number of sieve chips will permit a sieving rate that is several orders of magnitude faster than previous sieve systems. Each integrated circuit contributes combined processor and memory resources to the problem at hand, and operates independently of the other sieve chips. The sieve chips function as attached processors to a microprocessor. Currently, a printed circuit board is being developed containing a high performance microprocessor and sockets for 16 sieve chips. Multiple boards may be connected to a single general-purpose host computer through serial communication ports. This hierarchical approach to parallelism permits the use of a large number of sieve chips without incurring resource bottlenecks.