System, method and computer program product for performing a scan operation
A system, method, and computer program product are provided for efficiently performing a scan operation. In use, an array of elements is traversed by utilizing a parallel processor architecture. Such parallel processor architecture includes a plurality of processors each capable of physically executing a predetermined number of threads in parallel. For efficiency purposes, the predetermined number of threads of at least one of the processors may be executed to perform a scan operation involving a number of the elements that is a function (e.g. multiple, etc.) of the predetermined number of threads.
1. A method, comprising:
traversing an array of elements by utilizing a parallel processor architecture including a plurality of processors each capable of physically executing a predetermined number of threads in parallel; and
executing the predetermined number of threads of at least one of the processors to perform a scan operation involving a number of the elements that is a function of the predetermined number of threads, wherein the function includes a multiple that is at least two.
2. The method of claim 1 , wherein the threads each execute a single instruction on different data.
3. The method of claim 1 , wherein the parallel processor architecture includes a graphics processor.
4. The method of claim 1 , wherein the scan operation includes an all-prefix-sums operation.
5. The method of claim 1 , wherein the array of elements is traversed in a single direction.
6. The method of claim 1 , wherein the array of elements is traversed utilizing an XOR operation.
7. The method of claim 1 , wherein the scan operation is performed on a plurality of portions of the array each including a number of elements equal to the predetermined number.
8. The method of claim 7 , wherein the portions of the array are non-overlapping.
9. The method of claim 7 , wherein a synchronization is performed amongst the threads performing the scan operation on a first one of the portions, and the threads performing the scan operation on a second one of the portions.
10. The method of claim 7 , wherein results of the scan operation performed on the portions of the array are stored.
11. The method of claim 10 , wherein the results of the scan operation performed on the portions of the array are used to complete the scan operation.
12. A computer program product embodied on a non-transitory computer readable medium, comprising:
computer code for traversing an array of elements by utilizing a parallel processor architecture including a plurality of processors each capable of physically executing a predetermined number of threads in parallel; and
computer code for executing the predetermined number of threads of at least one of the processors to perform a scan operation involving a number of the elements that is a function of the predetermined number of threads, wherein the function includes a multiple that is at least two.
13. The computer program product of claim 12 , wherein the computer code is a component of a driver capable of providing general computational capabilities utilizing a graphics processor.
14. The computer program product of claim 12 , and further comprising computer code for traversing the array of elements in a single direction.
15. The computer program product of claim 12 , and further comprising computer code for traversing the array of elements utilizing an XOR operation.
16. A system, comprising:
a parallel processor architecture including a plurality of processors each capable of physically executing a predetermined number of threads in parallel; and
a driver in communication with the parallel processor architecture for executing the predetermined number of threads of at least one of the processors to perform a scan operation involving a number of array elements that is a function of the predetermined number of threads, wherein the function includes a multiple that is at least two.
17. The system of claim 16 , wherein the parallel processor architecture is coupled to memory via a bus.
18. The method of claim 1 , wherein each of the threads of a particular processor are assigned an element for performing a relevant scan operation.
19. The method of claim 1 , wherein each of the threads is assigned exactly one element to perform the scan operation upon, such that all of the threads of a particular processor terminate at the same time.
20. The computer program product of claim 12 , wherein the scan operation is performed on a plurality of portions of the array each including a number of elements equal to the predetermined number.
21. The system of claim 16 , wherein the scan operation is performed on a plurality of portions of the array each including a number of elements equal to the predetermined number.
22. The system of claim 16 , wherein the portions of the array are non-overlapping.