IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0830463
(2007-07-30)
|
등록번호 |
US-8090704
(2012-01-03)
|
발명자
/ 주소 |
- Archer, Charles Jens
- Peters, Amanda
- Ricard, Gary Ross
- Sidelnik, Albert
- Smith, Brian Edward
|
출원인 / 주소 |
- International Business Machines Corporation
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
2 인용 특허 :
20 |
초록
▼
An apparatus and method retrieves a database record from an in-memory database of a parallel computer system using a non-unique key. The parallel computer system performs a simultaneous search on each node of the computer system using the non-unique key and then utilizes a global combining network t
An apparatus and method retrieves a database record from an in-memory database of a parallel computer system using a non-unique key. The parallel computer system performs a simultaneous search on each node of the computer system using the non-unique key and then utilizes a global combining network to combine the local results from the searches of each node to efficiently and quickly search the entire database.
대표청구항
▼
1. A computer apparatus for searching an in-memory database comprising: a plurality of compute nodes each having a processor and computer memory operatively coupled to the processor, the computer memory having disposed within the computer memory a portion of the in-memory database, wherein the plura
1. A computer apparatus for searching an in-memory database comprising: a plurality of compute nodes each having a processor and computer memory operatively coupled to the processor, the computer memory having disposed within the computer memory a portion of the in-memory database, wherein the plurality of compute nodes further comprise a global combining network adapter (GCNA) for performing collective operations over a global combining network that connects the plurality of compute nodes in a binary tree where the plurality of compute nodes have a parent node and child nodes, wherein each of the plurality of compute nodes is assigned a unique rank which uniquely identifies the node's location in the binary tree network for use in both point to point and collective operations in the binary tree network,wherein the collective operations are variations or combinations of four operations comprising broadcast operation, gather operation, scatter operation and reduce operation,wherein the GCNA comprises an arithmetic logic unit (ALU) that operates on data in registers in the GCNA and stores the results in a results buffer;a search mechanism in the computer memory that receives a non-unique search key and searches the portion of the in-memory database using the search key and places a local result in a contribution buffer; andwherein the search mechanism contributes to a search of the in-memory database for the non-unique search key through a collective operation on the buffers of the global combining network by combining data received from a child node with the contents of the contribution buffer and passing over the GCNA a combined result to the parent node. 2. The computer apparatus of claim 1 further comprising a service node connected to the plurality of compute nodes that initiates a search of the in-memory database located within the plurality of compute nodes. 3. The computer apparatus of claim 1 wherein the search result is a bitmask created by an all reduce operation, where each bit in the bitmask represents a record in the database and an active bit represents a record that matches the search. 4. The computer apparatus of claim 1 wherein the search result comprises an integer vector and a results buffer, where each integer in the integer vector represents an offset into the results buffer and where the results buffer contains all records in the database matching the search. 5. The computer apparatus of claim 4 wherein the integer vector is created with a parallel prefix operation and the results buffer is created with an all reduce operation. 6. The computer apparatus of claim 1 wherein the compute nodes are located in a massively parallel computer system. 7. A computer implemented method for searching an in-memory database on a parallel computer system comprising the steps of: broadcasting a non-unique search key to a plurality of compute nodes, wherein the plurality of compute nodes comprise a processor, a memory and a global combining network adapter (GCNA), wherein the GCNA performs collective operations over a global combining network that connects the plurality of compute nodes in a binary tree with a parent node and child nodes a child node, wherein each of the plurality of compute nodes is assigned a unique rank which uniquely identifies the node's location in the binary tree network for use in both point to point and collective operations in the binary tree network,wherein the collective operations are variations or combinations of four operations comprising broadcast operation, gather operation, scatter operation and reduce operation,wherein the GCNA combines data received from the child nodes with local data and passes results to a parent node, wherein the GCNA comprises an arithmetic logic unit (ALU) that operates on data in registers in the GCNA and stores the results in a results buffer;initiating a search on each of the plurality of nodes using the search key;storing a local search result in a contribution combining network buffer;performing a collective operation using the GCNA on the plurality of compute nodes to combine data from the child nodes with the contribution buffer and passing a result stored in a results buffer to the parent node to create a database search result for searching the in-memory database for the non-unique search key. 8. The computer implemented method of claim 7 wherein the method is initiated from a service node connected to the plurality of compute nodes. 9. The computer implemented method of claim 7 wherein a contribution register and a results register connected to the ALU hold a portion of the contribution buffer and results buffer respectively. 10. The computer implemented method of claim 7 further comprising the steps of: allocating a bitmask;creating a bitmask for each node;performing the all reduce operation to “OR” the bitmasks of each node;performing a parallel prefix operation on the number of database records on each node;wherein the search result is a bitmask created by the all reduce operation, where each bit in the bitmask represents a record in the database and an active bit represents a record that matches the search. 11. The computer implemented method of claim 7 further comprising the steps of: allocating an integer vector;creating an integer vector value for each node based on local search results;performing a parallel prefix operation on the number of matching database records on each node;allocating search results to a results buffer;performing the all reduce operation on the result buffers on each node to create a complete results buffer where each node returns the actual data from the matching records from the local search, and wherein the parallel prefix operations provides a node boundary for each node in the complete results buffer. 12. A computer implemented method for searching an in-memory database on a parallel computer system comprising the steps of: allocating an integer vector;broadcasting a non-unique search key to a plurality of compute nodes, wherein the plurality of compute nodes comprise a processor, a memory and a global combining network adapter (GCNA), wherein the GCNA performs collective operations over a global combining network that connects the plurality of compute nodes in a binary tree with a parent node and child nodes, wherein each of the plurality of compute nodes is assigned a unique rank which uniquely identifies the node's location in the binary tree network for use in both point to point and collective operations in the binary tree network,wherein the collective operations are variations or combinations of four operations comprising broadcast operation, gather operation, scatter operation and reduce operation,wherein the GCNA combines data received from the child nodes with local data and passes results to the parent node, wherein the GCNA comprises an arithmetic logic unit (ALU) that operates on data in registers in the GCNA and stores the results in a results buffer;initiating a search on each of the plurality of nodes using the search key;creating an integer vector value for each node based on local search results;storing a local search result in a combining network buffer;performing an all reduce operation on the result buffers on each node using the GCNA to create a complete results buffer where each node returns the actual data from the matching records from the local search, and wherein the parallel prefix operations provides a node boundary for each node in the complete results buffer; andwherein a contribution register and a results register connected to the ALU hold a portion of the contribution buffer and results buffer respectively. 13. An article of manufacture for searching an in-memory database on a parallel computer, the article of manufacture comprising computer program instructions disposed upon a computer recordable medium, when executed by a computer processor performs the steps of: broadcasting a unique search key to a plurality of compute nodes, wherein the plurality of compute nodes comprise a processor, a memory and a global combining network adapter (GCNA), wherein the GCNA performs collective operations over a global combining network that connects each of the plurality of compute nodes in a binary tree with a parent node and child nodes, wherein each of the plurality of compute nodes is assigned a unique rank which uniquely identifies the node's location in the binary tree network for use in both point to point and collective operations in the binary tree network,wherein the collective operations are variations or combinations of four operations comprising broadcast operation, gather operation, scatter operation and reduce operation,wherein the GCNA combines data received from the child nodes with local data and passes results to the parent node, wherein the GCNA comprises an arithmetic logic unit (ALU) that operates on data in registers in the GCNA and stores the results in a results buffer;initiating a search on each of the plurality of nodes using the search key;storing a search result on each of the plurality of nodes in a contribution buffer;performing a collective operation on the combining network buffers on the plurality of nodes using the GCNA to combine data from the child nodes with the contribution buffer and passing a result stored in a results buffer to a parent node to create a search result for searching the in-memory database for the non-unique search key. 14. The article of manufacture of claim 13 wherein the method is initiated from a service node connected to the plurality of compute nodes. 15. The article of manufacture of claim 13 wherein the arithmetic logic unit (ALU) communicates with the parent node and the child nodes and performs the all reduce operation on data in the combining network buffers and wherein a contribution register and a results register connected to the ALU hold a portion of the contribution buffer and results buffer respectively. 16. The article of manufacture of claim 13 further comprising the steps of: allocating a bitmask;creating a bitmask for each node;performing an all reduce operation to “OR” the bitmasks of each node;performing the parallel prefix operation on the number of database records on each node;wherein the search result is a bitmask created by the all reduce operation, where each bit in the bitmask represents a record in the database and an active bit represents a record that matches the search. 17. The article of manufacture claim 13 further comprising the steps of: allocating an integer vector;creating an integer vector value for each node based on local search results;performing parallel prefix operation on the number of matching database records on each node;allocating search results to a results buffer;performing all reduce operation on the result buffers on each node to create a complete results buffer where each node returns the actual data from the matching records from the local search, and wherein the parallel prefix operations provides a node boundary for each node in the complete results buffer. 18. The article of manufacture of claim 13 wherein the compute nodes are located in a massively parallel computer system.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.