KR102544118B1 - Apparatus for a hash table to minimize hash conflict - Google Patents
Apparatus for a hash table to minimize hash conflictDownload PDFInfo
- Publication number
- KR102544118B1 KR102544118B1KR1020160051497AKR20160051497AKR102544118B1KR 102544118 B1KR102544118 B1KR 102544118B1KR 1020160051497 AKR1020160051497 AKR 1020160051497AKR 20160051497 AKR20160051497 AKR 20160051497AKR 102544118 B1KR102544118 B1KR 102544118B1
- Authority
- KR
- South Korea
- Prior art keywords
- hash
- key
- signal
- data
- bit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/22—Indexing; Data structures therefor; Storage structures
- G06F16/2228—Indexing structures
- G06F16/2255—Hash tables
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/10—Address translation
- G06F12/1009—Address translation using page tables, e.g. page table structures
- G06F12/1018—Address translation using page tables, e.g. page table structures involving hashing techniques, e.g. inverted page tables
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/10—File systems; File servers
- G06F16/13—File access structures, e.g. distributed indices
- G06F16/137—Hash-based
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/31—Indexing; Data structures therefor; Storage structures
- G06F16/316—Indexing structures
- G06F16/325—Hash tables
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Translated fromKoreanDescription
Translated fromKorean본 발명은 해시 충돌 최소화를 위한 해시 테이블 장치에 관한 것으로, 보다 상세하게는 제한된 하드웨어 리소스를 이용하여 해시 테이블을 구현하는 경우 해시 충돌을 최소화 할 수 있는 해시 충돌 최소화를 위한 해시 테이블 장치에 관한 것이다.The present invention relates to a hash table device for minimizing hash collisions, and more particularly, to a hash table device for minimizing hash collisions capable of minimizing hash collisions when a hash table is implemented using limited hardware resources.
해시 테이블(Hash table)은 컴퓨팅 분야에서 키를 값에 매핑하거나 연관 배열(Associative array) 등의 구현에 사용되는 데이터 구조이다. 네트워크 스위치나 라우터 등의 분야에서 고속으로 키를 값에 매핑하는 것이 필요한 경우 해시 테이블이 사용될 수 있다.A hash table is a data structure used in computing to map keys to values or implement associative arrays. A hash table can be used when it is necessary to map keys to values at high speed in the field of network switches or routers.
예를 들면, 네트워크 스위치에서는 맥 어드레스 러닝(Mac address learning)이라는 작업을 수행하는데, 각 포트 별로 유입되는 이더넷 프레임 내에 존재하는 소스 어드레스(Source address)를 키로 사용하여 포트 번호를 값으로 매핑시킨다. 이렇게 매핑된 포트 번호는 나중에 유입된 이더넷 프레임의 목적지(Destination)를 알아내는데 이용된다.For example, in a network switch, a task called Mac address learning is performed, and a port number is mapped to a value using a source address existing in an Ethernet frame flowing into each port as a key. The port number mapped in this way is used to find out the destination of the incoming Ethernet frame later.
또한, 라우터의 경우에는 맥 어드레스(Mac address) 대신에 IP번호를 키로써 사용한다. 스위치나 라우터의 경우 목적지를 고속으로 탐색해야 하기 때문에 메모리를 이용한 해시 테이블을 사용한다.Also, in the case of a router, an IP number is used as a key instead of a Mac address. In the case of a switch or router, a hash table using memory is used because the destination must be searched at high speed.
도 1은 종래 해시 테이블 장치를 나타내는 도면이다.1 is a diagram showing a conventional hash table device.
도 1을 참조하면, 해시 테이블 장치는 K개의 키(Key) 집합(100), 해시 함수부(110) 및 N개의 값 집합(120)을 포함한다. 여기서, 해시 테이블 장치는 K개의 키(Key) 집합(100)을 해시 함수부(110)라는 함수를 통해서 N개의 값 집합(120)에 매칭시킨다. 이때, K는 N보다 큰 수 이다.Referring to FIG. 1, the hash table device includes
여기서,함수부(110)는 길이가 긴 데이터를 정해진 길이의 데이터로 줄여주는 함수로 결정론적으로 작동해야 한다. 따라서, 각각의 해시 값이 다르다면, 해시 값에 대한 원래 데이터도 달라져야 한다.Here, the
그러나, 제1 키(Key #0)는 N개의 값 집합(120) 중에서 제3 값(Value #0)에 매칭되고, 제3 키(Key #2)도 N개의 값 집합(120) 중에서 제3 값(Value #0)에 매칭되므로, 해시 충돌(130)이 발생한다. 이에 따라 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 데이터를 검색하는 비용이 증가하게 되는 단점이 있다.However, the first key (Key #0) matches the third value (Value #0) among the
한편, 해시 충돌을 해결하기 위해 다양한 방법이 시도되고 있으며, 하드웨어 자원을 많이 사용할수록 충돌 확률을 줄일 수 있다. 특히, 메모리의 길이를 늘릴수록 해시 충돌 확률은 감소하게 된다. 하지만, 소형 네트워크 스위치나 라우터 등과 같은 제한된 하드웨어 자원이 허락되는 분야의 경우 메모리 자원을 무한정 늘리기에는 무리가 있다.Meanwhile, various methods have been tried to solve hash collisions, and the probability of collisions can be reduced as more hardware resources are used. In particular, as the memory length increases, the hash collision probability decreases. However, in the case of fields where limited hardware resources are allowed, such as small network switches or routers, it is unreasonable to increase memory resources indefinitely.
본 발명은 종래 해시 테이블 장치에 비해 제한된 하드웨어 리소스를 이용하여 해시 테이블을 구현하는 경우 해시 충돌을 최소화 할 수 있는 해시 충돌 최소화를 위한 해시 테이블 장치를 제공하는 것을 목적으로 한다.An object of the present invention is to provide a hash table device for minimizing hash collisions that can minimize hash collisions when a hash table is implemented using limited hardware resources compared to conventional hash table devices.
또한 본 발명은 종래 해시 테이블 장치에 비해 해시 충돌 발생시 데이터 검색 비용을 절감할 수 있는 해시 충돌 최소화를 위한 해시 테이블 장치를 제공하는 것을 목적으로 한다.Another object of the present invention is to provide a hash table device for minimizing hash collision, which can reduce data search costs when a hash collision occurs, compared to a conventional hash table device.
본 발명의 목적들은 이상에서 언급한 목적으로 제한되지 않으며, 언급되지 않은 본 발명의 다른 목적 및 장점들은 하기의 설명에 의해서 이해될 수 있고, 본 발명의 실시예에 의해 보다 분명하게 이해될 것이다. 또한, 본 발명의 목적 및 장점들은 특허 청구 범위에 나타낸 수단 및 그 조합에 의해 실현될 수 있음을 쉽게 알 수 있을 것이다.The objects of the present invention are not limited to the above-mentioned objects, and other objects and advantages of the present invention not mentioned above can be understood by the following description and will be more clearly understood by the examples of the present invention. It will also be readily apparent that the objects and advantages of the present invention may be realized by means of the instrumentalities and combinations indicated in the claims.
이러한 목적을 달성하기 위한 본 발명은 k 비트의 키(Key)를 입력 받아 n 비트의 어드레스를 각각 출력하는 복수의 해시 함수부, 상기 어드레스를 입력 받아 제1 및 제2 데이터 신호를 출력하는 듀얼 포트 메모리, 상기 키(Key)와 상기 제1 및 제2 데이터 신호의 k 비트 데이터를 입력 받아 상기 키(Key)와 상기 제1 및 제2 데이터 신호의 k 비트 데이터의 일치 여부를 비교하는 비교기, 상기 비교기의 출력 신호와 제1 및 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)가 있는지를 판별하는 키 판별부, 상기 비교기의 인버전 된 출력 신호와 상기 제1 및 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)의 해시 충돌 여부를 판단하는 해시 충돌 감지부, 상기 키 판별부의 출력 신호와 상기 해시 충돌 감지부의 출력 신호를 입력 받아 히트 신호, 충돌 신호, 유효 신호 및 제어 신호를 출력하는 신호 선택부 및 상기 제어 신호에 따라 상기 어드레스 신호와 상기 키(Key)의 매핑 값을 출력하는 멀티 플렉서를 포함하는 것을 특징으로 한다.The present invention for achieving this object is a plurality of hash function units for receiving a k-bit key and outputting an n-bit address, respectively, and a dual port for receiving the address and outputting first and second data signals. A memory, a comparator for receiving k-bit data of the key and the first and second data signals and comparing whether the key and k-bit data of the first and second data signals match, the A key determination unit for determining whether the key to be found exists in the dual port memory by ANDing the output signal of the comparator with the s-bit data of the first and second data signals, and the inverted output signal of the comparator A hash collision detecting unit for AND operation of s-bit data of the first and second data signals to determine whether the key to be found in the dual port memory hash collision, an output signal of the key determination unit and the hash collision Includes a signal selection unit that receives the output signal of the sensing unit and outputs a hit signal, a collision signal, a valid signal, and a control signal, and a multiplexer that outputs a mapping value between the address signal and the key according to the control signal It is characterized by doing.
본 발명에 따르면, 상기 해시 함수부는 상기 k 비트의 키(Key)를 n 비트의 제1 어드레스로 출력하는 제1 해시 함수부 및 상기 k 비트의 키(Key)를 n 비트의 제2 어드레스로 출력하는 제2 해시 함수부를 포함할 수 있다.According to the present invention, the hash function unit outputs the k-bit key to an n-bit first address and the k-bit key to an n-bit second address. It may include a second hash function unit that does.
또한 본 발명에 따르면, 상기 제1 및 제2 해시 함수부는 서로 다른 해시 함수를 포함할 수 있다.Also, according to the present invention, the first and second hash function units may include different hash functions.
또한 본 발명에 따르면, 상기 비교기는 상기 키(Key)와 상기 제1 데이터 신호의 k 비트 데이터를 입력 받아 상기 키(Key)와 상기 제1 데이터 신호의 k 비트 데이터의 일치 여부를 비교하는 제1 비교기 및 상기 키(Key)와 상기 제2 데이터 신호의 k 비트 데이터를 입력 받아 상기 키(Key)와 상기 제2 데이터 신호의 k 비트 데이터의 일치 여부를 비교하는 제2 비교기를 포함할 수 있다.In addition, according to the present invention, the comparator first receives the key (Key) and k-bit data of the first data signal and compares whether the key (Key) and k-bit data of the first data signal match. A comparator and a second comparator for receiving k-bit data of the key and the second data signal and comparing whether the key and k-bit data of the second data signal match.
또한 본 발명에 따르면, 상기 키 판별부는 상기 제1 비교기의 출력 신호와 제1 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)가 있는지를 판별하는 제1 키 판별부 및 상기 제2 비교기의 출력 신호와 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)가 있는지를 판별하는 제2 키 판별부를 포함할 수 있다.In addition, according to the present invention, the key determination unit performs an AND operation on the output signal of the first comparator and the s-bit data of the first data signal to determine whether the key to be found is present in the dual port memory. and a second key determination unit for determining whether the key to be found exists in the dual port memory by performing an AND operation on the output signal of the second comparator and the s-bit data of the second data signal.
또한 본 발명에 따르면, 상기 제1 및 제2 키 판별부는 상기 k 비트의 키와 상기 듀얼 포트 메모리의 내용이 일치하는 경우 히트(Hit) 신호를 출력하고, 상기 k 비트의 키와 상기 듀얼 포트 메모리의 내용이 일치하는 않는 경우 미스(Miss) 신호를 출력할 수 있다.In addition, according to the present invention, the first and second key discrimination units output a hit signal when the k-bit key and the contents of the dual-port memory match, and the k-bit key and the dual-port memory If the contents of do not match, a miss signal can be output.
또한 본 발명에 따르면, 상기 해시 충돌 감지부는 상기 제1 비교기의 인버전 된 출력 신호와 상기 제1 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)의 해시 충돌 여부를 판단하는 제1 해시 충돌 감지부 및 상기 제2 비교기의 인버전 된 출력 신호와 상기 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)의 해시 충돌 여부를 판단하는 제2 해시 충돌 감지부를 포함할 수 있다.In addition, according to the present invention, the hash collision detecting unit performs an AND operation on the inverted output signal of the first comparator and the s-bit data of the first data signal to obtain a hash collision of the key to be found in the dual port memory. Hash collision of the key to be found in the dual port memory by performing an AND operation on the inverted output signal of the first hash collision detection unit and the second comparator for determining whether or not the s-bit data of the second data signal It may include a second hash collision detection unit for determining whether or not.
또한 본 발명에 따르면, 상기 제1 해시 충돌 감지부는 상기 제1 데이터 신호의 s 비트 데이터가 ‘1’이면 해시 충돌이 발생한 것으로 판단할 수 있다.Also, according to the present invention, the first hash collision detecting unit may determine that a hash collision has occurred when the s-bit data of the first data signal is '1'.
또한 본 발명에 따르면, 상기 제2 해시 충돌 감지부는 상기 제2 데이터 신호의 s 비트 데이터가 ‘0’이면 상기 키(Key)의 매핑 값과 상기 제2 데이터 신호의 s 비트 데이터를 ‘1’로 하여 상기 듀얼 포트 메모리에 각각 기입할 수 있다.In addition, according to the present invention, the second hash collision detector sets the mapping value of the key and the s-bit data of the second data signal to '1' when the s-bit data of the second data signal is '0'. Thus, each of the dual port memories can be written.
또한 본 발명에 따르면, 상기 신호 선택부는 상기 제1 및 제2 키 판별부의 출력 신호와 상기 제1 및 제2 해시 충돌 감지부의 출력 신호를 입력 받아 히트 신호, 충돌 신호, 유효 신호 및 제1 및 제2 제어 신호를 출력할 수 있다.In addition, according to the present invention, the signal selection unit receives the output signals of the first and second key determination units and the output signals of the first and second hash collision detecting units, and receives a hit signal, a collision signal, a valid signal, and a first and second hash collision detection unit. 2 control signals can be output.
또한 본 발명에 따르면, 상기 멀티 플렉서는 상기 제1 및 제2 어드레스 신호를 입력 받으며, 상기 제1 제어 신호에 따라 상기 제1 및 제2 어드레스 신호 중 어느 하나를 어드레스로 출력하는 제1 멀티 플렉서 및 상기 제1 및 제2 데이터 신호의 v 비트 데이터를 입력 받으며, 상기 제2 제어 신호에 따라 상기 상기 제1 및 제2 데이터 신호의 v 비트 데이터 중 어느 하나를 상기 키(Key)의 매핑 값으로 출력할 수 있다.In addition, according to the present invention, the multiplexer receives the first and second address signals and outputs one of the first and second address signals as an address according to the first control signal. Receives v-bit data of the lexer and the first and second data signals, and converts one of the v-bit data of the first and second data signals to a mapping value of the key according to the second control signal can be output as
전술한 바와 같이 본 발명에 의한 해시 테이블 장치는 종래 해시 테이블 장치에 비해 서로 다른 해시 테이블을 사용하여 해시 충돌을 최소화 할 수 있는 장점이 있다.As described above, the hash table device according to the present invention has the advantage of minimizing hash collision by using different hash tables compared to the conventional hash table device.
또한 본 발명에 의한 해시 테이블 장치는 종래 해시 테이블 장치에 비해 제한된 리소스를 사용하여 해시 테이블을 구현할 수 있는 장점이 있다.In addition, the hash table device according to the present invention has the advantage of being able to implement a hash table using limited resources compared to the conventional hash table device.
또한 본 발명에 의한 해시 테이블 장치는 종래 해시 테이블 장치에 비해 해시 충돌 발생시 데이터 검색 비용을 절감할 수 있는 장점이 있다.In addition, the hash table device according to the present invention has the advantage of reducing data search costs when hash collision occurs compared to the conventional hash table device.
도 1은 종래 해시 테이블 장치를 나타내는 도면이다.
도 2는 본 발명의 일 실시예에 따른 해시 충돌 최소화를 위한 해시 테이블 장치를 나타내는 도면이다.
도 3은 본 발명의 일 실시예에 따른 신호 선택부의 진리표를 나타낸다.1 is a diagram showing a conventional hash table device.
2 is a diagram illustrating a hash table device for minimizing hash collisions according to an embodiment of the present invention.
3 shows a truth table of a signal selector according to an embodiment of the present invention.
전술한 목적, 특징 및 장점은 첨부된 도면을 참조하여 상세하게 후술되며, 이에 따라 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자가 본 발명의 기술적 사상을 용이하게 실시할 수 있을 것이다. 본 발명을 설명함에 있어서 본 발명과 관련된 공지 기술에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 상세한 설명을 생략한다. 이하, 첨부된 도면을 참조하여 본 발명에 따른 바람직한 실시예를 상세히 설명하기로 한다. 도면에서 동일한 참조부호는 동일 또는 유사한 구성요소를 가리키는 것으로 사용된다.The above objects, features and advantages will be described later in detail with reference to the accompanying drawings, and accordingly, those skilled in the art to which the present invention belongs will be able to easily implement the technical spirit of the present invention. In describing the present invention, if it is determined that the detailed description of the known technology related to the present invention may unnecessarily obscure the subject matter of the present invention, the detailed description will be omitted. Hereinafter, preferred embodiments according to the present invention will be described in detail with reference to the accompanying drawings. In the drawings, the same reference numerals are used to indicate the same or similar components.
도 2는 본 발명의 일 실시예에 따른 해시 충돌 최소화를 위한 해시 테이블 장치를 나타내는 도면이다. 도 3은 본 발명의 일 실시예에 따른 신호 선택부의 진리표를 나타낸다.2 is a diagram illustrating a hash table device for minimizing hash collisions according to an embodiment of the present invention. 3 shows a truth table of a signal selector according to an embodiment of the present invention.
도 2를 참조하면, 본 발명의 일 실시예에 따른 해시 테이블 장치는 k 비트의 키(Key)를 입력 받아 n 비트의 어드레스(Address)로 각각 출력하는 제1 및 제2 해시 함수부(140, 240), 키의 매핑 값(Mapping value)을 저장하는 듀얼 포트 메모리(Dual port memory)(200), 키의 매핑 값의 일치 여부를 판단하는 제1 및 제2 비교기(160, 260), 듀얼 포트 메모리(200)에 키의 존재 유무를 판별하는 제1 및 제2 키 판별부(170, 270), 키의 해시 충돌 여부를 감지하는 제1 및 제2 해시 충돌 감지부(180, 280), 제1 및 제2 키 판별부(170, 270)와 제1 및 제2 해시 충돌 감지부(180, 280)의 출력 신호를 입력 받는 신호 선택부(190) 및 제1 및 제2 해시 함수(140, 240)에서 출력되는 각각의 어드레스를 입력 받는 제1 및 제2 멀티플렉서(320, 340)를 포함한다.Referring to FIG. 2, the hash table device according to an embodiment of the present invention receives a k-bit key and outputs an n-bit address, respectively, first and second
제1 및 제2 해시 함수부(140, 240)는 k 비트의 키(Key)가 입력되면 n 비트의 제1 및 제2 어드레스(Address #0, Address #1)를 출력한다. 여기서, 제1 및 제2 해시 함수부(140, 240)는 서로 다른 해시 함수일 수 있다.The first and second
이에 따라 제1 및 제2 해시 함수부(140, 240)는 서로 다른 방법으로 동작하므로 이들에 의하여 생성된 제1 및 제2 어드레스(Address #0, Address #1)가 중복될 가능성은 현저히 떨어지게 된다.Accordingly, since the first and second
따라서, 제1 해시 함수부(140)에 의해서 얻어진 제1 어드레스(Address #0)의 데이터가 충돌이 발생하더라도 제2 해시 함수부(240)에 의해서 얻어진 제2 어드레스(Address #1)의 영역이 비어 있다면, 제2 어드레스(Address #1)에 해당하는 키(Key)의 매핑 값을 기입할 수 있다.Therefore, even if the data of the first address (Address #0) obtained by the first
또한, 제1 및 제2 해시 함수부(140, 240)는 예를 들면, 소형 스위치나 라우터에서는 비교적 연산이 간단한 CRC를 이용하거나 체크섬(Check sum) 함수 또는 XOR 폴딩(Folding) 방식을 사용할 수 있다. 그리고, 제1 및 제2 해시 함수부(140, 240)는 CRC(Cyclic redundant code)나 MD5(Message-Digest algorithm 5), SHA(Secure hash algorithm) 등의 함수를 포함할 수 있다.In addition, the first and second
여기서, CRC는 미가공 데이터의 우발적 인 변경을 검출하기 위해 디지털 네트워크, 저장 장치에 사용되는 오류 검출코드이다. MD5는 128비트 암호화 해시 함수로서, 주로 프로그램이나 파일이 원본 그대로인지를 확인하는 무결성 검사 등에 사용된다. SHA는 암호학적 해시 함수들의 모음으로, 보안 프로토콜 및 프로그램에서 사용된다.Here, CRC is an error detection code used in digital networks and storage devices to detect accidental alteration of raw data. MD5 is a 128-bit cryptographic hash function, and is mainly used for integrity checks to check whether a program or file is original. SHA is a collection of cryptographic hash functions, used in secure protocols and programs.
듀얼 포트 메모리(200)는 2n의 길이를 가지며, 서로 다른 위치의 데이터를 읽을 수 있다. 또한, 듀얼 포트 메모리(200)는 제1 및 제2 어드레스(Address #0, Address #1)을 각각 입력 받아 제1 및 제2 데이터 신호(Data #0, Data #1)를 출력할 수 있다.The
여기서, 제1 및 제2 데이터 신호(Data #0, Data #1)는 각각 (k+v+s) 비트일 수 있다. 이때, k 비트는 키(Key)이고, v 비트는 키(Key)에 해당하는 매핑 값이고, s 비트는 해당 메모리 번지의 내용이 유효한지를 나타내는 유효 비트이다.Here, each of the first and second data signals
그리고, 제1 및 제2 데이터 신호(Data #0, Data #1)는 제1 및 제2 히트 신호(Hit #0,Hit #1), 제1 및 제2 충돌 신호(Conflict #0, Conflict #1), 제1 및 제2 유효 비트(Sig #0, Sig #1)를 생성하는데 사용된다.In addition, the first and second data signals
제1 비교기(160)는 k 비트의 키(Key)와 듀얼 포트 메모리(200)에 저장되어 있는 제1 데이터 신호(Data #0)의 k 비트를 입력 받아 키(Key)와 제1 데이터 신호(Data #0)의 k 비트의 일치 여부를 비교한다.The
제2 비교기(260)는 k 비트의 키(Key)와 듀얼 포트 메모리(200)에 저장되어 있는 제2 데이터 신호(Data #1)의 k 비트를 입력 받아 키(Key)와 제2 데이터 신호(Data #1)의 k 비트의 일치 여부를 비교한다.The
제1 키 판별부(170)는 제1 비교기(160)의 출력 신호와 제1 데이터 신호(Data #0)의 s 비트를 AND 연산하여 듀얼 포트 메모리(200) 내에 찾고자 하는 키(Key)가 있는지를 판별한다. 이때, 제1 키 판별부(170)는 입력된 k 비트의 키(Key)와 듀얼 포트 메모리(200)의 내용이 일치하는 경우 히트(Hit) 신호를 출력한다. 그러나, 제1 키 판별부(170)는 입력된 k 비트의 키와 듀얼 포트 메모리(200)의 내용이 일치하는 않는 경우 미스(Miss) 신호를 출력 한다.The first
제2 키 판별부(270)는 제2 비교기(260)의 출력 신호와 제2 데이터 신호(Data #1)의 s 비트를 AND 연산하여 듀얼 포트 메모리(200) 내에 찾고자 하는 키(Key)가 있는지를 판별한다. 제1 키 판별부(170)와 마찬가지로 제2 키 판별부(270)는 입력된 k 비트의 키(Key)와 듀얼 포트 메모리(200)의 내용이 일치하는 경우 히트(Hit) 신호를 출력한다. 그러나, 제2 키 판별부(170)는 입력된 k 비트의 키와 듀얼 포트 메모리(200)의 내용이 일치하는 않는 경우 미스(Miss) 신호를 출력한다.The second
제1 해시 충돌 감지부(180)는 제1 비교기(160)의 인버전(Inversion) 된 출력 신호와 제1 데이터 신호(Data #0)의 s 비트를 AND 연산하여 듀얼 포트 메모리(200) 내에 찾고자 하는 키(Key)의 해시 충돌 여부를 판단한다.The first hash
제2 해시 충돌 감지부(280)는 제2 비교기(260)의 인버전(Inversion) 된 출력 신호와 제2 데이터 신호(Data #1)의 s 비트를 AND 연산하여 듀얼 포트 메모리(200) 내에 찾고자 하는 키(Key)의 해시 충돌 여부를 판단한다.The second hash
여기서, 듀얼 포트 메모리(200)에 저장된 키(Key)와 입력된 키(Key)가 다르지만, 제1 데이터 신호(Data #0)의 s 비트가 ‘1’이라면, 해시 충돌이 발생한 것으로 판단한다. 만약, 제2 데이터 신호(Data #1)의 s 비트가 ‘0’이라면, 듀얼 포트 메모리(200)의 해당 번지에는 데이터가 비어 있으므로 제2 어드레스(Address #1)을 이용하여 해당 번지에 키(Key)에 해당하는 매핑 값과 제2 데이터 신호(Data #0, Data #1)의 s 비트를 ‘1’로 하여 듀얼 포트 메모리(200)에 각각 기입할 수 있다.Here, if the key stored in the
신호 선택부(190)는 제1 및 제2 히트 신호(Hit #0,Hit #1) 및 제1 및 제2 충돌 신호(Conflict #0, Conflict #1)를 입력 받아 히트 신호(Hit), 충돌 신호(Conflict), 유효 신호(Valid) 및 제1 및 제2 제어 신호(Con #0, Con #1)를 출력한다. 여기서, 제1 및 제2 제어 신호(Con #0, Con #1)는 제1 및 제2 멀티 플렉서(320, 340)로 각각 입력된다.The
도 3을 참조하면, 신호 선택부(190)에 입력되는 제1 히트 신호(Hit #0)와 제1 충돌 신호(Conflict #0)는 동시에 ‘1’이 발생할 수 없으며, 제2 히트 신호(Hit #1)와 제2 충돌 신호(Conflict #1)도 동시에 ‘1’이 발생할 수 없다. 또한, 제1 히트 신호(Hit #0)와 제2 히트 신호(Hit #1)도 동시에 ‘1’이 발생할 수 없다. 그 이유는 히트(Hit)가 발생하지 않은 경우에만 듀얼 포트 메모리(200)에 키(Key)의 매핑 값을 업데이트(Update) 하기 때문이다.Referring to FIG. 3 , '1' cannot occur simultaneously between the first hit signal (Hit #0) and the first collision signal (Conflict #0) input to the
따라서, 제1 히트 신호(Hit #0)와 제1 충돌 신호(Conflict #0)가 각각 ‘1’인 경우, 제2 히트 신호(Hit #1)와 제2 충돌 신호(Conflict #1)가 각각 ‘1’인 경우, 제1 및 제2 히트 신호(Hit #0, Hit #1)가‘1’인 경우를 미발생 조건이라고 표기 하였다.Therefore, when the first hit
제1 및 제2 멀티 플렉서(320, 340)는 신호 선택부(190)로부터 출력되는 제1 및 제2 제어 신호(Con #0, Con #1)를 각각 입력 받는다. 이때, 제1 멀티 플렉서(320)는 제1 제어 신호(Con #0)에 따라 제1 및 제2 어드레스(Address #0, Address #1) 중 어느 하나를 어드레스 신호(Address)로 출력한다. 그리고, 제2 멀티 플렉서(340)는 제2 제어 신호(Con #1)에 따라 제1 및 제2 데이터 신호(Data #0, Data #1) 중 어느 하나를 키(Key)의 매핑 값(Value)으로 출력한다.The first and
전술한 바와 같은 본 발명에 의한 해시 테이블 장치는 종래 해시 테이블 장치에 비해 서로 다른 해시 테이블을 사용하여 해시 충돌을 최소화 할 수 있는 장점이 있다.As described above, the hash table device according to the present invention has the advantage of minimizing hash collision by using different hash tables compared to the conventional hash table device.
또한 본 발명에 의한 해시 테이블 장치는 종래 해시 테이블 장치에 비해 제한된 리소스를 사용하여 해시 테이블을 구현할 수 있는 장점이 있다.In addition, the hash table device according to the present invention has the advantage of being able to implement a hash table using limited resources compared to the conventional hash table device.
또한 본 발명에 의한 해시 테이블 장치는 종래 해시 테이블 장치에 비해 해시 충돌 발생시 데이터 검색 비용을 절감할 수 있는 장점이 있다.In addition, the hash table device according to the present invention has the advantage of reducing data search costs when hash collision occurs compared to the conventional hash table device.
전술한 본 발명은, 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에게 있어 본 발명의 기술적 사상을 벗어나지 않는 범위 내에서 여러 가지 치환, 변형 및 변경이 가능하므로 전술한 실시예 및 첨부된 도면에 의해 한정되는 것이 아니다.The above-described present invention, since various substitutions, modifications, and changes are possible to those skilled in the art without departing from the technical spirit of the present invention, the above-described embodiments and accompanying drawings is not limited by
140: 제1 해시 함수부160: 제1 비교기
170: 제1 키 판별부180: 제1 해시 충돌 감지부
190: 신호 선택부200: 듀얼 포트 메모리
240: 제2 해시 함수부260: 제2 비교기
270: 제2 키 판별부280: 제2 해시 충돌 감지부
320: 제1 멀티플렉서340: 제2 멀티 플렉서140: first hash function unit 160: first comparator
170: first key determination unit 180: first hash collision detection unit
190: signal selector 200: dual port memory
240: second hash function unit 260: second comparator
270: second key determination unit 280: second hash collision detection unit
320: first multiplexer 340: second multiplexer
Claims (11)
Translated fromKorean상기 어드레스 신호를 입력 받아 제1 및 제2 데이터 신호를 출력하는 듀얼 포트 메모리;
상기 키(Key)와 상기 제1 및 제2 데이터 신호의 k 비트의 데이터를 입력 받아 상기 키(Key)와 상기 제1 및 제2 데이터 신호의 k 비트의 데이터 일치 여부를 비교하는 비교기;
상기 비교기의 출력 신호와 제1 및 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)가 있는지를 판별하는 키 판별부;
상기 비교기의 인버전 된 출력 신호와 상기 제1및 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)의 해시 충돌 여부를 판단하는 해시 충돌 감지부;
상기 키 판별부의 출력 신호와 상기 해시 충돌 감지부의 출력 신호를 입력 받아 히트 신호, 충돌 신호, 유효 신호 및 제어 신호를 출력하는 신호 선택부; 및
상기 제어 신호에 따라 상기 어드레스 신호와 상기 키(Key)의 매핑 값을 출력하는 멀티 플렉서를 포함하는 해시 충돌 최소화를 위한 해시 테이블 장치.a plurality of hash function units for receiving a k-bit key and outputting n-bit address signals, respectively;
a dual port memory receiving the address signal and outputting first and second data signals;
a comparator that receives the key and k-bit data of the first and second data signals and compares whether the key and k-bit data of the first and second data signals match;
a key discriminating unit which performs an AND operation on the output signal of the comparator and the s-bit data of the first and second data signals to determine whether the key to be found exists in the dual port memory;
a hash collision detecting unit configured to perform an AND operation on the inverted output signal of the comparator and the s-bit data of the first and second data signals to determine whether or not the key to be found within the dual port memory has hash collision;
a signal selection unit receiving the output signal of the key determining unit and the output signal of the hash collision detecting unit and outputting a hit signal, a collision signal, a valid signal, and a control signal; and
A hash table device for minimizing hash collisions comprising a multiplexer outputting a mapping value between the address signal and the key according to the control signal.
상기 해시 함수부는 상기 k 비트의 키(Key)를 n 비트의 제1 어드레스로 출력하는 제1 해시 함수부; 및
상기 k 비트의 키(Key)를 n 비트의 제2 어드레스로 출력하는 제2 해시 함수부를 포함하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 1,
The hash function unit includes a first hash function unit outputting the k-bit key to an n-bit first address; and
A hash table device for minimizing hash collisions comprising a second hash function unit outputting the k-bit key to an n-bit second address.
상기 제1 및 제2 해시 함수부는 서로 다른 해시 함수를 포함하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 2,
The first and second hash function units haveh table devices for hash collision minimization including different hash functions.
상기 비교기는 상기 키(Key)와 상기 제1 데이터 신호의 k 비트 데이터를 입력 받아 상기 키(Key)와 상기 제1 데이터 신호의 k 비트 데이터의 일치 여부를 비교하는 제1 비교기; 및
상기 키(Key)와 상기 제2 데이터 신호의 k 비트 데이터를 입력 받아 상기 키(Key)와 상기 제2 데이터 신호의 k 비트 데이터의 일치 여부를 비교하는 제2 비교기를 포함하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 1,
The comparator may include: a first comparator for receiving k-bit data of the key and the first data signal and comparing whether the key and k-bit data of the first data signal match; and
For hash collision minimization including a second comparator for receiving the key and k-bit data of the second data signal and comparing whether the key and k-bit data of the second data signal match Hash table device.
상기 키 판별부는 상기 제1 비교기의 출력 신호와 제1 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)가 있는지를 판별하는 제1 키 판별부; 및
상기 제2 비교기의 출력 신호와 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)가 있는지를 판별하는 제2 키 판별부를 포함하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 4,
The key discriminating unit performs an AND operation on the output signal of the first comparator and the s-bit data of the first data signal to determine whether the key to be found exists in the dual port memory; and
A hash for minimizing hash collision including a second key determination unit configured to perform an AND operation on the output signal of the second comparator and the s-bit data of the second data signal to determine whether the key to be found exists in the dual port memory. table device.
상기 제1 및 제2 키 판별부는 상기 k 비트의 키와 상기 듀얼 포트 메모리의 내용이 일치하는 경우 히트(Hit) 신호를 출력하고, 상기 k 비트의 키와 상기 듀얼 포트 메모리의 내용이 일치하는 않는 경우 미스(Miss) 신호를 출력하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 5,
The first and second key determination units output a hit signal when the k-bit key and the contents of the dual-port memory match, and when the k-bit key and the contents of the dual-port memory do not match A hash table device for minimizing hash collisions that outputs a miss signal in case of a miss.
상기 해시 충돌 감지부는 상기 제1 비교기의 인버전 된 출력 신호와 상기 제1 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)의 해시 충돌 여부를 판단하는 제1 해시 충돌 감지부; 및
상기 제2 비교기의 인버전 된 출력 신호와 상기 제2 데이터 신호의 s 비트 데이터를 AND 연산하여 상기 듀얼 포트 메모리 내에 찾고자 하는 상기 키(Key)의 해시 충돌 여부를 판단하는 제2 해시 충돌 감지부를 포함하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 4,
The hash collision detecting unit performs an AND operation on the inverted output signal of the first comparator and the s-bit data of the first data signal to determine whether the key to be found in the dual port memory hash collision 1st hash collision detector; and
A second hash collision detecting unit for determining whether the key to be found in the dual port memory hash collision by performing an AND operation on the inverted output signal of the second comparator and the s-bit data of the second data signal. A hash table device for minimizing hash collisions.
상기 제1 해시 충돌 감지부는 상기 제1 데이터 신호의 s 비트 데이터가 ‘1’이면 해시 충돌이 발생한 것으로 판단하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 7,
The first hash collision detection unit determines that a hash collision has occurred when the s-bit data of the first data signal is '1'.
상기 제2 해시 충돌 감지부는 상기 제2 데이터 신호의 s 비트 데이터가 ‘0’이면 상기 키(Key)의 매핑 값과 상기 제2 데이터 신호의 s 비트 데이터를 ‘1’로 하여 상기 듀얼 포트 메모리에 각각 기입하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 8,
The second hash collision detection unit sets the mapping value of the key and the s-bit data of the second data signal to '1' when the s-bit data of the second data signal is '0', and stores the data in the dual-port memory. A hash table device for minimizing hash collisions with each write.
상기 신호 선택부는 상기 제1 및 제2 키 판별부의 출력 신호와 상기 제1 및 제2 해시 충돌 감지부의 출력 신호를 입력 받아 히트 신호, 충돌 신호, 유효 신호 및 제1 및 제2 제어 신호를 출력하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 1,
The signal selector receives the output signals of the first and second key determination units and the output signals of the first and second hash collision detecting units and outputs a hit signal, a collision signal, a valid signal, and first and second control signals. Hash table device for minimizing hash collisions.
상기 멀티 플렉서는 제1 및 제2 어드레스 신호를 입력 받으며, 상기 제1 제어 신호에 따라 상기 제1 및 제2 어드레스 신호 중 어느 하나를 어드레스로 출력하는 제1 멀티 플렉서; 및
상기 제1 및 제2 데이터 신호의 v 비트 데이터를 입력 받으며, 상기 제2 제어 신호에 따라 상기 상기 제1 및 제2 데이터 신호의 v 비트 데이터 중 어느 하나를 상기 키(Key)의 매핑 값으로 출력하는 제2 멀티 플렉서를 포함하는 해시 충돌 최소화를 위한 해시 테이블 장치.According to claim 10,
a first multiplexer that receives first and second address signals and outputs one of the first and second address signals as an address according to the first control signal; and
It receives v-bit data of the first and second data signals, and outputs one of the v-bit data of the first and second data signals as a mapping value of the key according to the second control signal. A hash table device for minimizing hash collisions comprising a second multiplexer that does.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020160051497AKR102544118B1 (en) | 2016-04-27 | 2016-04-27 | Apparatus for a hash table to minimize hash conflict |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020160051497AKR102544118B1 (en) | 2016-04-27 | 2016-04-27 | Apparatus for a hash table to minimize hash conflict |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20170122481A KR20170122481A (en) | 2017-11-06 |
| KR102544118B1true KR102544118B1 (en) | 2023-06-16 |
Family
ID=60384076
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020160051497AActiveKR102544118B1 (en) | 2016-04-27 | 2016-04-27 | Apparatus for a hash table to minimize hash conflict |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR102544118B1 (en) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112997161B (en) | 2018-06-18 | 2025-02-21 | Flc技术集团股份有限公司 | Method and apparatus for using a storage system as a main memory |
| JP2022011449A (en)* | 2020-06-30 | 2022-01-17 | 富士通株式会社 | Arithmetic processing program, arithmetic processing method, and arithmetic processing device |
| CN116547655A (en)* | 2020-09-03 | 2023-08-04 | Flc技术集团股份有限公司 | Hash function with pre-scrambler |
| US12164788B2 (en) | 2021-11-15 | 2024-12-10 | Samsung Electronics Co., Ltd. | System on chip and operation method thereof |
| US12287829B2 (en) | 2023-02-23 | 2025-04-29 | International Business Machines Corporation | Minimizing hash collisions of composite keys |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6282629B1 (en) | 1992-11-12 | 2001-08-28 | Compaq Computer Corporation | Pipelined processor for performing parallel instruction recording and register assigning |
| KR100656354B1 (en) | 2005-08-19 | 2006-12-11 | 한국전자통신연구원 | Method and apparatus for storing pattern matching data and method of performing pattern matching using same |
| US20080034115A1 (en) | 2006-08-01 | 2008-02-07 | Yuan-Sun Chu | Apparatus for handling hash collisions of hash searching and method using the same |
| US20130114414A1 (en) | 2011-11-08 | 2013-05-09 | Futurewei Technologies, Inc. | Hardware-Based Dynamic Load Balancing That Avoids Flow Packet Reordering Statistically |
| US20140067830A1 (en) | 2005-03-03 | 2014-03-06 | Washington University | Method and Apparatus for Performing Similarity Searching |
| US20150169467A1 (en) | 2013-12-13 | 2015-06-18 | Oracle International Corporation | Systems and Methods for Rapidly Generating Suitable Pairs of Hash Functions |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100994328B1 (en) | 2008-05-02 | 2010-11-12 | 닉스테크 주식회사 | Program blocking method and device using hash table |
| KR101956031B1 (en)* | 2012-10-15 | 2019-03-11 | 삼성전자 주식회사 | Data compressor, memory system comprising the compress and method for compressing data |
- 2016
- 2016-04-27KRKR1020160051497Apatent/KR102544118B1/enactiveActive
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6282629B1 (en) | 1992-11-12 | 2001-08-28 | Compaq Computer Corporation | Pipelined processor for performing parallel instruction recording and register assigning |
| US20140067830A1 (en) | 2005-03-03 | 2014-03-06 | Washington University | Method and Apparatus for Performing Similarity Searching |
| KR100656354B1 (en) | 2005-08-19 | 2006-12-11 | 한국전자통신연구원 | Method and apparatus for storing pattern matching data and method of performing pattern matching using same |
| US20080034115A1 (en) | 2006-08-01 | 2008-02-07 | Yuan-Sun Chu | Apparatus for handling hash collisions of hash searching and method using the same |
| US20130114414A1 (en) | 2011-11-08 | 2013-05-09 | Futurewei Technologies, Inc. | Hardware-Based Dynamic Load Balancing That Avoids Flow Packet Reordering Statistically |
| US20150169467A1 (en) | 2013-12-13 | 2015-06-18 | Oracle International Corporation | Systems and Methods for Rapidly Generating Suitable Pairs of Hash Functions |
Also Published As
| Publication number | Publication date |
|---|---|
| KR20170122481A (en) | 2017-11-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR102544118B1 (en) | Apparatus for a hash table to minimize hash conflict | |
| US8880554B2 (en) | Method and apparatus for high performance, updatable, and deterministic hash table for network equipment | |
| US7290083B2 (en) | Error protection for lookup operations in content-addressable memory entries | |
| US9280609B2 (en) | Exact match lookup scheme | |
| US6434662B1 (en) | System and method for searching an associative memory utilizing first and second hash functions | |
| US6910118B2 (en) | Table management technique | |
| US10803040B2 (en) | Efficient and accurate lookups of data by a stream processor using a hash table | |
| US7827218B1 (en) | Deterministic lookup using hashed key in a multi-stride compressed trie structure | |
| US9392005B2 (en) | System and method for matching pattern | |
| US10091137B2 (en) | Apparatus and method for scalable and flexible wildcard matching in a network switch | |
| CN112447254B (en) | Error Detection Method in Ternary Content Addressable Memory | |
| US7345897B2 (en) | Error protected ternary content-addressable memories and lookup operations performed thereon | |
| JP2004054935A (en) | Method and device for detecting bit error in maskable content addressable memory | |
| US10218643B2 (en) | Apparatus and method for scalable and flexible access control list lookup in a network switch | |
| US11720492B1 (en) | Algorithmic TCAM with compressed key encoding | |
| US6947301B2 (en) | Content addressable memory (CAM) device employing a recirculating shift register for data storage | |
| US10795580B2 (en) | Content addressable memory system | |
| US7716416B2 (en) | Analysis for a multiple tag hit in a content addressable memory (CAM) | |
| US20170010814A1 (en) | Memory with compressed key | |
| CN113051569A (en) | Virus detection method and device, electronic equipment and storage medium | |
| US7266004B2 (en) | Identifying content-addressable memory entries differing from a lookup word in multiple but less than a predetermined number of bit positions | |
| CN110781100B (en) | Data detection method, logic chip and network equipment | |
| US6976123B2 (en) | Priority resolver and “near match” detection circuit | |
| JP6888234B2 (en) | Search device, search program, and search method | |
| US20090043956A1 (en) | Mapping an input data value to a resultant data value |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application | Patent event code:PA01091R01D Comment text:Patent Application Patent event date:20160427 | |
| PG1501 | Laying open of application | ||
| A201 | Request for examination | ||
| PA0201 | Request for examination | Patent event code:PA02012R01D Patent event date:20201231 Comment text:Request for Examination of Application Patent event code:PA02011R01I Patent event date:20160427 Comment text:Patent Application | |
| E902 | Notification of reason for refusal | ||
| PE0902 | Notice of grounds for rejection | Comment text:Notification of reason for refusal Patent event date:20221221 Patent event code:PE09021S01D | |
| E701 | Decision to grant or registration of patent right | ||
| PE0701 | Decision of registration | Patent event code:PE07011S01D Comment text:Decision to Grant Registration Patent event date:20230609 | |
| GRNT | Written decision to grant | ||
| PR0701 | Registration of establishment | Comment text:Registration of Establishment Patent event date:20230612 Patent event code:PR07011E01D | |
| PR1002 | Payment of registration fee | Payment date:20230613 End annual number:3 Start annual number:1 | |
| PG1601 | Publication of registration |