Along with process technology advancement, we can integrate more and more on-chip memory in an SOC. Memory intensive applications, such as image processing and digital signal processing, usually access certain number of data arrays. Memory system designs for such systems can then critically influence cost, performance, and power of the resulting SOCs. In this thesis research, we focus on the software design of a memory synthesis method of data stored in arrays. Memory synthesis task considers access time, power, and cost requirements of array data and utilize characteristics of indexing patterns of array accesses. It then derive the allocation of memory organizations and effective organizations of multiple data arrays mapped onto the allocated memory modules. Its design principle lies in the matching of data array reorganization and their assigned memory module resource allocation so as to enhance data access locality in the same memory rows and to reduce the number of row accesses (bit line accesses). Hence, we can achieve required power and performance goals with low memory system cost. Static memory synthesis solves memory synthesis problem with fixed loop count and tasks in prior of product design. The memory synthesis task succeeds the high level synthesis task. It is then followed by the address generating circuit design task and the memory access scheduling circuit design task of the functional module side. These circuit designs can herein be combined with high level synthesis results to perform logic synthesis. Finally, we can perform physical synthesis of functional modules, logic circuit modules, and memory modules. It is thus expected to produce an SOC design satisfying overall design requirements. The software design of the static memory synthesis method includes two main topics: memory allocation and module assignment for data arrays and the estimation method of a memory system design. In this research, we designed the experimental software for the memory synthesis method. We also planned experiments based upon real and synthetic design cases to validate the effectiveness of the static memory synthesis method.

Attacks on the heap are an increasingly severe threat. State-of-the-art secure dynamic memory allocators can offer protection, however their memory consumption is high, making them suboptimal in many situations. We introduce sys, a secure allocator whose design is driven by memory efficiency. Among other features, sys uses an efficient fine-grain size classes indexing mechanism and implements a novel dynamic canary scheme. It offers a low memory overhead due its size classes optimized for canary usage, its on-demand metadata allocation, and the combination of randomized allocations and over-provisioning into a single memory efficient security feature. sys protects against widespread heap-related attacks such as overflows, over-reads, double/invalid free, and use-after-free. Evaluation over a wide range of applications shows that it offers a significant reduction in memory consumption compared to the state-of-the-art secure allocator (up to 2x in macro-benchmarks), while offering similar or better security guarantees and good performance. / Master of Science / Attacks targeting on the runtime memory (heap allocator) are severe threats to software safety. Statistical results shown that the numbers of heap-related attacks has doubled since 2016. A large number of research works are designed to solve the security problems by offering different techniques to prevent some specific attacks. Not only are they very secure but also fast. However, these secure heap allocators sacrifice the memory usage, all of them at least double the memory consumption. Our work is trying to design and implement a heap allocator, in which it can defend against different attacks, as well as fast and memory-efficient. We carefully re-design some security features in our heap allocator while keep memory-efficient in mind. In the end, we evaluated sys and found that it offers significant reduction on different benchmarks suites. Evaluation also showed that sys can detect a lot of vulnerabilities in the software, while offer the same good performance as the state-of-the-art heap allocator.

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.

Dynamic memory allocators are a determining factor of an application's performanceand have the opportunity to improve a major performance bottleneck ontoday's computer hardware: data locality. To approach this problem, a memoryallocator must rst oer strategies that allow the locality problem to be addressed.However, while focusing on locality, an allocator must also not ignore the existing constraintsof allocation speed and fragmentation, which further complicate its design. Inorder for a locality improving technique to be successfully employed in today's largecode applications, its integration needs to be automatic, without user intervention.The alternative, manual integration, is not a tractable solution.In this dissertation we develop three novel memory allocators that explore dierentallocation strategies that enhance an application's locality. We conduct the rststudy that shows that allocation speed, fragmentation and locality improving goalsare antagonistic. We develop an automatic method that supplies allocation hintsfrom C++ STL containers to their allocators. This method allows applications tobenet from locality improving techniques at the cost of a simple re-compilation. Weconduct the rst study that quanties the eect of allocation hints on performance,and show that an allocator with high locality of reference can be as competitive asone using an application's spatial feedback.To further allow dynamic memory allocation to improve an application's performance,new and non-traditional strategies need be explored. We develop a generic software tool that allows users to examine unconventional strategies. The tool allowsusers not only to focus on allocation strategies rather than their implementation, butalso to compare and contrast various approaches.

Dynamic memory allocators are a determining factor of an application's performanceand have the opportunity to improve a major performance bottleneck ontoday's computer hardware: data locality. To approach this problem, a memoryallocator must rst oer strategies that allow the locality problem to be addressed.However, while focusing on locality, an allocator must also not ignore the existing constraintsof allocation speed and fragmentation, which further complicate its design. Inorder for a locality improving technique to be successfully employed in today's largecode applications, its integration needs to be automatic, without user intervention.The alternative, manual integration, is not a tractable solution.In this dissertation we develop three novel memory allocators that explore dierentallocation strategies that enhance an application's locality. We conduct the rststudy that shows that allocation speed, fragmentation and locality improving goalsare antagonistic. We develop an automatic method that supplies allocation hintsfrom C++ STL containers to their allocators. This method allows applications tobenet from locality improving techniques at the cost of a simple re-compilation. Weconduct the rst study that quanties the eect of allocation hints on performance,and show that an allocator with high locality of reference can be as competitive asone using an application's spatial feedback.To further allow dynamic memory allocation to improve an application's performance,new and non-traditional strategies need be explored. We develop a generic software tool that allows users to examine unconventional strategies. The tool allowsusers not only to focus on allocation strategies rather than their implementation, butalso to compare and contrast various approaches.

This work presents a static instruction allocation scheme for the precision timed architecture’s (PRET) scratchpad memory. Since PRET provides timing instructions to control the temporal execution of programs, the objective of the allocation scheme is to ensure that the explicitly specified temporal requirements are met. Furthermore, this allocation incorporates instructions from multiple hardware threads of the PRET architecture. We formulate the allocation as an integer-linear programming problem, and we implement a tool that takes binaries, constructs a control-flow graph, performs the allocation, rewrites the binary with the new allocation, and generates an output binary for the PRET architecture. We carry out experiments on a modified version of the Malardalen benchmarks to illustrate that commonly known ACET and WCET based approaches cannot be directly applied to meet explicit timing requirements. We also show the advantage of performing the allocation across multiple threads. We present a real time benchmark controlling an Unmanned Air Vehicle as the case study.

Multi-processor computers are becoming increasingly popular and are important for improving application performance. Providing high-performance memory-management is important for multi-threaded programs. This thesis looks at memory allocation of dynamic-allocation memory in concurrent C and C++ programs. The challenges facing the design of any memory allocator include minimizing fragmentation, and promoting good locality. A multi-threaded memory-allocator is also concerned with minimizing contention, providing mutual exclusion, avoiding false-sharing, and preventing heap-blowup (a form of fragmentation). Several potential features are identified in existing multi-threaded memory-allocators. These features include per-thread heaps with a global heap, object ownership, object containers, thread-local free-list buffers, remote free-lists, allocation buffers, and lock-free operations. When used in different combinations, these features can solve most of the challenges facing a multi-threaded memory-allocator. Through the use of a test suite composed of both single and multi-threaded benchmark programs, several existing memory allocators and a set of new allocators are compared. It is determined that different features address different multi-threaded issues in the memory allocator with respect to performance, scaling, and fragmentation. Finally, recommendations are made for the design of a general-purpose memory-allocator.

Multi-processor computers are becoming increasingly popular and are important for improving application performance. Providing high-performance memory-management is important for multi-threaded programs. This thesis looks at memory allocation of dynamic-allocation memory in concurrent C and C++ programs. The challenges facing the design of any memory allocator include minimizing fragmentation, and promoting good locality. A multi-threaded memory-allocator is also concerned with minimizing contention, providing mutual exclusion, avoiding false-sharing, and preventing heap-blowup (a form of fragmentation). Several potential features are identified in existing multi-threaded memory-allocators. These features include per-thread heaps with a global heap, object ownership, object containers, thread-local free-list buffers, remote free-lists, allocation buffers, and lock-free operations. When used in different combinations, these features can solve most of the challenges facing a multi-threaded memory-allocator. Through the use of a test suite composed of both single and multi-threaded benchmark programs, several existing memory allocators and a set of new allocators are compared. It is determined that different features address different multi-threaded issues in the memory allocator with respect to performance, scaling, and fragmentation. Finally, recommendations are made for the design of a general-purpose memory-allocator.

Scratchpad Memory (SPM) is an alternative to cache. With SPM, the CPU¡¦s fast internal memory (ie, the SRAM) is directly mapped into the memory address space. This has the advantages of reduced power (by avoiding the memory management Unit, MMU, that a cache need to manage its tags and evictions), reduced area (for the same reason), and predictability.[1] Predictability is important in real-time systems, because each task must be assigned a deadline. If a task finishes early, there is no benefit. But if a task finishes late, then the effect is undesirable or even catastrophic. This means that the worst-case execution time (WCET) is more important than average-case execution time (ACET). The disadvantage of SPM, when compared to cache, is that the SPM requires software management of the fast memory. In a previous student¡¦s work from our laboratory, [3], an SPM allocator was presented for WCET-targeted compilation. Compared to that work, this current thesis make four key contributions. First, it introduces a significant amount of code infrastructure to allow library variables to be allocated to SPM. These variables turn out to represent a majority of all data accesses in many programs. Second, this provides support for allocating variables within recursive programs. Third, we support allocation of temporary variable (PC-relative addressing). Fourth, we have developed a simulator to obtain cycle-accurate information on memory behavior. In [3], the costs of allocation were not modeled, nor were the behaviors of the ARM¡¦s complex memory subsystem. Keywords: SPM, memory allocation, memory modeling, library variables, WCET

Scratchpad memory (SPM) is popular for real-time embedded systems. Whereas caches use a memory management unit (MMU) to control which data accesses go to the fast, on-chip SRAM, SPM directly maps certain addresses to the SRAM. One advantage of SPM is that it avoids the cache¡¦s costly MMU. Another advantage is that the SPM is 100% statically predictable, whereas the variables stored in the cache depend upon the dynamic execution history. This predictability is beneficial for real-time systems which must schedule tasks to finish by fixed deadlines. To set these deadlines, system designers must determine the worst-case execution times (WCETs) of the applications. The predictability of SPM makes these WCETs easier to measure. This thesis presents a new method for allocating stack and global data to the SPM. It is the first method to make use of the special properties of non-escaping variables so as to increase the effective size of the SPM. Our insight is that many local variables of caller functions can be temporarily swapped out of the SPM while the callee function executes. Ours is also the first method to support profiled WCET measurements in the allocation strategy. Most previous SPM methods optimize only for the average-case execution time (ACET), despite the fact that SPMs are often used in real-time environments where the WCET is also important. This new memory allocation strategy is also the first to be WCET/ACET tunable, a feature that is particular useful for soft real-time systems. Only one previous work considers a WCET-targeted SPM allocator. That work, however, only applies to static WCET analysis tools. Such tools are difficult to program and are not widely used. Also, they only have application to the most safety-critical of real-time systems. In contrast, our approach is the first to employ measurement-based WCET analysis (such as is most commonly used in industry) for SPM allocation.