All-To-All Comparisons on Architectures Having Limited Storage Space

Abstract

Mechanisms for performing all-to-all comparisons on architectures having limited storage space are provided. The mechanisms determine a number of data elements to be included in each set of data elements to be sent to each processing element of a data processing system, and perform a comparison operation on at least one set of data elements. The comparison operation comprises sending a first request to main memory for transfer of a first set of data elements into a local memory associated with the processing element and sending a second request to main memory for transfer of a second set of data elements into the local memory. A pair wise comparison computation of the all-to-all comparison of data elements operation is performed at approximately a same time as the second set of data elements is being transferred from main memory to the local memory.

1 . A method, in a data processing system having a plurality of processing elements, for performing a portion of an All-to-All comparison of data elements operation, comprising:
 determining a number of data elements to be included in each set of data elements to be sent to each processing element of the plurality of processing elements;   performing a comparison operation, of a portion of the All-to-All comparison of data elements operation assigned to a processing element, on at least one set of data elements, wherein the comparison operation comprises:
 sending, from the processing element, a first request to main memory for transfer of a first set of data elements into a local memory associated with the processing element; 
 sending, from the processing element, a second request to main memory for transfer of a second set of data elements into the local memory; and 
 performing a pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, at approximately a same time as the second set of data elements is being transferred from main memory to the local memory; and 
   storing results of the comparison operation in main memory of the data processing system.   
     
     
         2 . The method of  claim 1 , wherein the number of data elements to be included in each set of data elements is determined by a runtime test that determines a number of data elements that minimizes execution time of the All-to-All comparison of data elements operation. 
     
     
         3 . The method of  claim 1 , wherein the number of data elements to be included in each set of data elements is determined by a runtime test that selects a number of data elements that balances the interests of load-balancing among the processing elements in the plurality of processing elements, minimizing a number of messages exchanged between the processing elements and main memory, and overlapping computation performed by the processing elements with communication between the processing elements and main memory. 
     
     
         4 . The method of  claim 1 , wherein, in response to the pair wise comparison computation being a first pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the first set of data elements with each other data element in the first set of data elements. 
     
     
         5 . The method of  claim 1 , wherein, in response to the pair wise comparison computation being a last pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the second set of data elements with each other data element in the second set of data elements. 
     
     
         6 . The method of  claim 1 , wherein, in response to the pair wise comparison computation not being a first pair wise comparison and not being a last pair wise comparison of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the first set of data elements with each data element in a third set of data elements, the third set of data elements having been already retrieved into the local memory associated with the processing element as the second set of data elements of a previous comparison operation performed by the processing element. 
     
     
         7 . The method of  claim 1 , wherein performing the pair wise comparison computation comprises computing a Jaccard coefficient for pairs of data elements. 
     
     
         8 . The method of  claim 1 , wherein storing results of the comparison operation comprises storing the results of a comparison of a first data element with a second data element at a location indexed by the value (n*i)−(i*(i+1))/2−i−1+j, where i is the index of the first data element, j is the index of the second element, and n is the number of data elements to be included in each set of data elements to be sent to each processing element of the plurality of processing elements. 
     
     
         9 . The method of  claim 1 , wherein the data processing system is a heterogeneous multiprocessor system comprising at least one control processor and at least one controlled processor, wherein the at least one control processor and the at least one controlled processor have different instruction sets. 
     
     
         10 . The method of  claim 9 , wherein the processing elements in the plurality of processing elements are controlled processors. 
     
     
         11 . A computer program product comprising a computer recordable medium having a computer readable program recorded thereon, wherein the computer readable program, when executed on a computing device having a plurality of processing elements, causes the computing device to:
 determine a number of data elements to be included in each set of data elements to be sent to each processing element of the plurality of processing elements;   perform a comparison operation, of a portion of an All-to-All comparison of data elements operation assigned to a processing element, on at least one set of data elements, wherein the comparison operation comprises:
 sending, from the processing element, a first request to main memory for transfer of a first set of data elements into a local memory associated with the processing element; 
 sending, from the processing element, a second request to main memory for transfer of a second set of data elements into the local memory; and 
 performing a pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, at approximately a same time as the second set of data elements is being transferred from main memory to the local memory; and 
   store results of the comparison operation in main memory of the computing device.   
     
     
         12 . The computer program product of  claim 11 , wherein the number of data elements to be included in each set of data elements is determined by a runtime test that determines a number of data elements that minimizes execution time of the All-to-All comparison of data elements operation. 
     
     
         13 . The computer program product of  claim 11 , wherein the number of data elements to be included in each set of data elements is determined by a runtime test that selects a number of data elements that balances the interests of load-balancing among the processing elements in the plurality of processing elements, minimizing a number of messages exchanged between the processing elements and main memory, and overlapping computation performed by the processing elements with communication between the processing elements and main memory. 
     
     
         14 . The computer program product of  claim 11 , wherein, in response to the pair wise comparison computation being a first pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the first set of data elements with each other data element in the first set of data elements. 
     
     
         15 . The computer program product of  claim 11 , wherein, in response to the pair wise comparison computation being a last pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the second set of data elements with each other data element in the second set of data elements. 
     
     
         16 . The computer program product of  claim 11 , wherein, in response to the pair wise comparison computation not being a first pair wise comparison and not being a last pair wise comparison of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the first set of data elements with each data element in a third set of data elements, the third set of data elements having been already retrieved into the local memory associated with the processing element as the second set of data elements of a previous comparison operation performed by the processing element. 
     
     
         17 . The computer program product of  claim 11 , wherein performing the pair wise comparison computation comprises computing a Jaccard coefficient for pairs of data elements. 
     
     
         18 . The computer program product of  claim 11 , wherein the computing device stores results of the comparison operation by storing the results of a comparison of a first data element with a second data element at a location indexed by the value (n*i)−(i*(i+1))/2−i−1+j, where i is the index of the first data element, j is the index of the second element, and n is the number of data elements to be included in each set of data elements to be sent to each processing element of the plurality of processing elements. 
     
     
         19 . An apparatus, comprising:
 a control processor;   a plurality of controlled processors coupled to the control processor;   a plurality of local memories, each local memory being associated with a controlled processor of the plurality of controlled processors; and   a main memory coupled to the plurality of controlled processors, wherein the control processor determines a number of data elements to be included in each set of data elements to be sent to each controlled processor of the plurality of controlled processors, and wherein a processor in the plurality of processors;   perform a comparison operation, of a portion of an All-to-All comparison of data elements operation assigned to a controlled processor, on at least one set of data elements, wherein the comparison operation comprises:
 sending, from the controlled processor, a first request to main memory for transfer of a first set of data elements into a local memory associated with the controlled processor; 
 sending, from the controlled processor, a second request to main memory for transfer of a second set of data elements into the local memory; and 
 performing, by the controlled processor, a pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, at approximately a same time as the second set of data elements is being transferred from main memory to the local memory; and 
   store results of the comparison operation in main memory of the apparatus.   
     
     
         20 . The apparatus of  claim 19 , wherein:
 in response to the pair wise comparison computation being a first pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the first set of data elements with each other data element in the first set of data elements,   in response to the pair wise comparison computation being a last pair wise comparison computation of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the second set of data elements with each other data element in the second set of data elements, and   in response to the pair wise comparison computation not being a first pair wise comparison and not being a last pair wise comparison of the portion of the All-to-All comparison of data elements operation, performing the pair wise comparison computation comprises comparing each data element in the first set of data elements with each data element in a third set of data elements, the third set of data elements having been already retrieved into the local memory associated with the processing element as the second set of data elements of a previous comparison operation performed by the processing element.