Efficient Pipelined Binary Search

a pipelined, binary search technology, applied in the field of pipelined hardware, can solve the problem of high speed repetitive binary searching, and achieve the effect of reducing the number of pipelined binary searches

Inactive Publication Date: 2013-05-16
IXIA
View PDF6 Cites 21 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Benefits of technology

This patent describes a pipelined hardware for performing a binary search of an ordered list of data items. The search engine includes multiple stages, each with a memory, to compare the search key with the data items in the list. The search is performed by comparing the key to the middle value in the list and making a new estimate of the position of the key in the list. The search is done by iteratively comparing the key to the middle value in the list until the final value is reached. The number of comparisons required for a binary search is a logarithmic function of the number of data items in the list. The patent also describes the graphical representation of an ordered list and the block diagram of a pipelined binary search engine. The technical effect of this patent is to provide a faster and more efficient way to perform binary searches of ordered lists of data items.

Problems solved by technology

However, in some applications, such as routing data items within a communications network or generating traffic to test a communications network, high speed repetitive binary searching may be required.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0017]Description of Apparatus

[0018]FIG. 1 is a graphical representation of an exemplary ordered list 100, which is necessary background information for understanding subsequent descriptions. The ordered list 100 contains sixteen values, identified as D0 to DF using hexadecimal notation. D0 is the smallest value in the ordered list and DF is the largest value. Each of the other values in the list is larger than the preceding value and smaller than the succeeding value. An ordered list containing sixteen values was chosen for ease of description. An ordered list may contain substantially more than sixteen values.

[0019]The ordered list may be divided into an upper half, and a lower half, each containing eight values. D8 is the smallest value in the upper half of the ordered list 100, and D7 is the largest value in the lower half of the ordered list 100. The significance of these values will be discussed subsequently.

[0020]FIG. 2 is a block diagram of a pipelined binary search engine 2...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

An apparatus and machine readable storage medium for performing a binary search of an ordered list containing 2N values, where N is an integer greater than one. The apparatus may include a pipeline having N stages numbered 1 to N in sequence. Stage M of the pipeline, where M is in integer from 1 to N, may include a memory storing 2M-1 values from the ordered list, a comparator to compare the key to a value read from the memory based on comparison results from previous stages in the pipeline, and a result storage register to store a comparison result from the comparator and the comparison results from the previous stages in the pipeline.

Description

NOTICE OF COPYRIGHTS AND TRADE DRESS[0001]A portion of the disclosure of this patent document contains material which is subject to copyright protection. This patent document may show and / or describe matter which is or may become trade dress of the owner. The copyright and trade dress owner has no objection to the facsimile reproduction by anyone of the patent disclosure as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright and trade dress rights whatsoever.BACKGROUND[0002]1. Field[0003]This disclosure relates to pipelined hardware for performing a binary search of an ordered list of data items.[0004]2. Description of the Related Art[0005]Searching an ordered list of data items is a common task. For example, a telephone directory is a list of subscribers' names in alphabetical order. A typical manual search in a telephone directory may be performed by opening the directory to an estimated position, comparing a target name with...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Applications(United States)
IPC IPC(8): G06F17/30
CPCG06F17/30988G06F16/90348
Inventor PEPPER, GERALDHUANG, SEAN
Owner IXIA
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap