THE DERIVATION OF A HIGH SPEED SIEVE DEVICE
Date
1992-03-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science