A simple self-timed implementation of a priority queue for dictionary search problems

Author

Muhtaroglu, Ali ; Sezer, Omer Berat

Author_Institution

Middle East Tech. Univ., Kalkanli, Cyprus

fYear

2009

fDate

14-16 Jan. 2009

Firstpage

34

Lastpage

39

Abstract

This paper describes a sparse priority queue suitable for reporting the results from a sequence database search, using a self-timed protocol. The prioritization is simplified through an insertion sort scheme with no greater/less than logic. The resulting implementation promises to be compact, fast, and suitable for the specified application area. The architectural design has been validated on a prototype platform with Altera Cyclone II field programmable gate array (FPGA).

Keywords

database theory; dictionaries; field programmable gate arrays; protocols; queueing theory; search problems; sorting; Altera Cyclone II field programmable gate array; FPGA; architectural design; dictionary search problems; insertion sort scheme; self-timed protocol; sequence database search; sparse priority queue; Circuits; Clocks; Databases; Dictionaries; Field programmable gate arrays; Hardware; Logic; Protocols; Prototypes; Search problems; Hardware sorter; insertion sort; priority queue; self-timed queue;

fLanguage

English

Publisher

ieee

Conference_Titel

Adaptive Science & Technology, 2009. ICAST 2009. 2nd International Conference on

Conference_Location

Accra

ISSN

0855-8906

Print_ISBN

978-1-4244-3522-7

Electronic_ISBN

0855-8906

Type

conf

DOI

10.1109/ICASTECH.2009.5409749

Filename

5409749