Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

A method and system for ultra-parallel comparison

An algorithm and table entry technology, which can be used in other database retrieval, special data processing applications, and other database queries, etc., and can solve problems such as differences in natural language data and image data comparison requirements, and incompatibility with biological comparisons.

Active Publication Date: 2022-02-11
丁贤根
View PDF6 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0012] Although TCAM can achieve single-cycle comparison of tens of millions of data, its original intention is for the routing table of the router, which is seriously different from the comparison requirements of biological data, natural language data, and image data, and does not meet the requirements of biological comparison. right request

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

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • A method and system for ultra-parallel comparison
  • A method and system for ultra-parallel comparison
  • A method and system for ultra-parallel comparison

Examples

Experimental program
Comparison scheme
Effect test

specific Embodiment 1

[0189] Specific embodiment one: Biological sequence ultra-parallel comparison server

[0190] 1. Description of the module structure diagram

[0191] Such as Figure 5 It is an embodiment of the biological sequence super-parallel alignment server of the present invention. In the figure, two comparison units are used, among which the comparison unit 1 is larger, the entry width is 256 bytes, the depth is 1M entry rows, and 1 million entry rows are compared at a time in a single cycle; the comparison unit 2 is smaller, the entry width is 64 bytes, the depth is 16, and 16 entry lines are compared at a time in a single cycle. If it is a SAM file for biological sequences, the alignment can be done in Byte units. At this time, the following method is used: figure 2 The logical definition of the byte-based alignment unit shown, and Figure 4 Alignment array of and Figure 5 It is also a logical definition based on a byte-based comparison array; otherwise, it is a logical defini...

specific Embodiment 2

[0355] Specific embodiment two: PCIE card type overspeed comparison system

[0356] Such as Image 6 As shown, this embodiment is another application of the present invention—the PCIE card type overspeed comparison system. What is the same as the previous embodiment will not be repeated here, and only the difference is emphasized here.

[0357] 1. Use TCAM chip or FPGA to design PCIE card type super speed comparison system. The system includes: comparator array, management module, shift controller, reconfigurable logic, memory and table entry mapping, and PCIE interface.

[0358] 2. This system needs to be inserted into the PCIE slot of the PC to run, and it does not have the ability to run independently.

[0359] 3. The system includes a comparison unit, which uses the built-in CPU and program design of the TCAM chip as the management module of the system.

[0360] 4. The management module of this system designs a management interface for the host PC.

[0361] 5. The ent...

specific Embodiment 3

[0362] Specific embodiment three: general data overspeed comparison system

[0363] Such as Image 6 As shown, this embodiment is another application of the present invention—a general data overspeed comparison system. What is the same as the previous embodiment will not be repeated here, and only the difference is emphasized here.

[0364] 1, Figure 4 The alignment array is defined using bit-alignment-based logic, such as figure 1 shown.

[0365] Therefore, for the step S109, the logic defines that the position is a bit, and the comparison is a bit-by-bit comparison in units of bits.

[0366]2. For the comparison of image data, the width of the table item is suitable for the image size. For example, based on the 4K RGB three primary color video image format, when each picture is 3840*2160 pixels, the width of the table item is determined to be 3840*3* 24bits=270Kbits, the entry depth is 2160*3*24bits=151875bits=152Kbits, and the depth of the entry can also be increased....

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

Use FPGA, programmable logic or TCAM chips to design a single-cycle super-parallel comparison method to achieve simultaneous bit-by-bit comparison between key items and multiple table item lines within a single logic cycle, and output the matching table item line address , along with similarity and difference statistics and location information. The algorithm supports table item reconfiguration, similarity and difference processing, filter filtering, table entry mapping, one-dimensional array, comparison of two-dimensional data and multi-dimensional data; the system includes comparator array, reconfigurable logic, similarity and difference processing device, mapped memory, filter, communication interface. It can constitute an independent comparison server and PCIE accelerator card. This method is more than 10 times faster than the Fung computer comparison algorithm of the fastest CPU when comparing 10M entries. 9 Magnitude.

Description

technical field [0001] The invention relates to the fields of information technology and bioengineering, in particular to the fields of gene engineering, biological sequence alignment in protein engineering, and the fields of natural language and image recognition. Background technique [0002] Biological sequence comparison, natural language processing and image comparison are emerging disciplines. After searching and researching, the inventor found that almost all of the existing comparison technologies are Fung’s computer comparison algorithms. Some attempts to use GPU parallel algorithms, Its limitations are too large, and it cannot really achieve high-speed parallel comparison of specific data. [0003] TCAM (Ternary Content Addressable Memory, tri-state content addressable memory), it uses bit comparison technology, so that after a huge number of memories are arranged, they can be compared with a specific memory at the same time in a single cycle, and output the first ...

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 Patents(China)
IPC IPC(8): G06F16/903
CPCG06F16/90339G06F16/90344
Inventor 丁远彤丁贤根
Owner 丁贤根
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

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

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com