THE DERIVATION OF A HIGH SPEED SIEVE DEVICE

Simple item page
dc.contributor.authorPatterson, Cameron Douglaseng
dc.date.accessioned2008-05-20T23:30:02Z
dc.date.available2008-05-20T23:30:02Z
dc.date.computerscience1999-05-27eng
dc.date.issued1992-03-01eng
dc.description.abstractSieving 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.eng
dc.description.notesWe are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.caeng
dc.identifier.department1992-469-7eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/31369
dc.identifier.urihttp://hdl.handle.net/1880/46539
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleTHE DERIVATION OF A HIGH SPEED SIEVE DEVICEeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
1992-469-7.pdf
Size:
11.93 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description:
Download
Collections
Science Research & Publications