System and method for memory bandwidth friendly sorting on multi-core architectures
US8463820B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 26, 2009 |
| Grant date | Jun 11, 2013 |
| Priority date | — |
| Expiry date | Dec 4, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/0802
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
In some embodiments, the invention involves utilizing a tree merge sort in a platform to minimize cache reads/writes when sorting large amounts of data. An embodiment uses blocks of pre-sorted data residing in “leaf nodes” residing in memory storage. A pre-sorted block of data from each leaf node is read from memory and stored in faster cache memory. A tree merge sort is performed on the nodes that are cache resident until a block of data migrates to a root node. Sorted blocks reaching the root node are written to memory storage in an output list until all pre-sorted data blocks have been moved to cache and merged upward to the root. The completed output list in memory storage is a list of the fully sorted data. Other embodiments are described and claimed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.