Software applications’ performance is hindered by a variety of factors, but most notably by the well-known CPU-memory speed gap (often known as the memory wall). This results in the CPU sitting idle waiting for data to be brought from memory to processor caches. The addressing used by caches cause non-uniform accesses to various cache sets. The non-uniformity is due to several reasons, including how different objects are accessed by the code and how the data objects are located in memory. Memory allocators determine where dynamically created objects are placed, thus defining addresses and their mapping to cache locations. It is important to evaluate how different allocators behave with respect to the localities of the created objects. Most allocators use a single attribute, the size, of an object in making allocation decisions. Additional attributes such as the placement with respect to other objects, or specific cache area may lead to better use of cache memories. In this dissertation, we proposed and implemented a framework that allows for the development and evaluation of new memory allocation techniques. At the root of the framework is a memory tracing tool called Gleipnir, which provides very detailed information about every memory access, and relates it back to source level objects. Using the traces from Gleipnir, we extended a commonly used cache simulator for generating detailed cache statistics: per function, per data object, per cache line, and identify specific data objects that are conflicting with each other. The utility of the framework is demonstrated with a new memory allocator known as equivalence class allocator. The new allocator allows users to specify cache sets, in addition to object size, where the objects should be placed. We compare this new allocator with two well-known allocators, viz., Doug Lea and Pool allocators.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

<p> This thesis defends the use of genetic algorithms (GA) to solve the maximum number of repetitions in a binary string. Repetitions in strings have significant uses in many different fields, whether it is data-mining, pattern-matching, data compression or computational biology 14]. Main extended the definition of repetition, he realized that in some cases output could be reduced because of overlapping repetitions, that are simply rotations of one another [10]. As a result, he designed the notion of a run to capture the maximal leftmost repetition that is extended to the right as much as possible. Franek and Smyth independently computed the same number of maximum repetition for strings of length five to 35 using an exhaustive search method. Values greater than 35 were not computed because of the exponential increase in time required. Using GAs we are able to generate string with very large, if not the maximum, number of runs for any string length. The ability to generate strings with large runs is an advantage for learning more about the characteristics of these strings. </p> / Thesis / Master of Science (MSc)