Multi-core architectures have become the main trend in the last decade in microprocessor design in order to deliver increasing computing power in computing systems. This trend in microprocessor architecture is leading towards the increment of the number of processing cores in the same die, thanks to transistor miniaturisation, with tens to hundreds of cores integrated in a system in the near future. Moreover, multi-core architectures have become pervasive in computing devices at all levels, from smartphones and tablets to multi-user servers and supercomputers. A multi-core architecture poses a challenge in software application development, since sequential applications can no longer benefit from new multi-core generations. Alternative programming models, tools and algorithms are needed in order to efficiently exploit computing power inherent in multi-core architectures. This thesis presents map-merge, a parallel processing method to formulate parallel versions of software applications that classify and process large input data arrays. Map-merge uses and advantages are illustrated with a parallel formulation of a generic bucket sort algorithm, which gives a peak speedup gain of 9 when it is executed in a dual 6-core system; and also with a parallel formulation of a branch predictor simulator, which gives a peak speedup gain of 7 in the same multi-core system. In addition, two methods, based on bit-representation and bit-manipulation strategies, are presented: bit-slice as an alternative algorithm to rank elements in a set, and bit-index as an alternative algorithm to sort a set of integers. The bit-slice method is implemented as an application to compute the median from a set of integers. This implementation outperformed median calculation versions by up to 6 times. These versions are based on two sorting algorithms: quicksort and counting sort. On the other hand, the bit-index method is implemented as a sorting algorithm for permutations of a set of integers. The approach also outperformed quicksort and counting sort implementations with peak speedup gains of 10 and 6 respectively. These methods are inspired by traditional
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:628531 |
| Date | January 2014 |
| Creators | Quintal, Luis Fernando Curi |
| Publisher | University of Reading |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0022 seconds