The Experts below are selected from a list of 5448 Experts worldwide ranked by ideXlab platform
Maged M Michael - One of the best experts on this subject based on the ideXlab platform.
-
PLDI 2004: Scalable Lock-Free Dynamic Memory Allocation
Sigplan Notices, 2015Co-Authors: Maged M MichaelAbstract:Dynamic Memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, and programming flexibility. A lock-free Memory allocator guarantees progress regardless of whether some threads are delayed or even killed and regardless of scheduling policies. This paper presents a completely lockfree Memory allocator. It uses only widely-available operating system support and hardware atomic instructions. It offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to deadlock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. Also, by leveraging some high-level structures from Hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing. In addition, our allocator allows finer concurrency and much lower latency than Hoard. We use PowerPC shared Memory multiprocessor systems to compare the performance of our allocator with the default AIX 5.1 libc malloc, and two widely-used multithread allocators, Hoard and Ptmalloc. Our allocator outperforms the other allocators in virtually all cases and often by substantial margins, under various levels of parallelism and Allocation patterns. Furthermore, our allocator also offers the lowest contention-free latency among the allocators by significant margins
-
scalable lock free Dynamic Memory Allocation
Programming Language Design and Implementation, 2004Co-Authors: Maged M MichaelAbstract:Dynamic Memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, and programming flexibility. A lock-free Memory allocator guarantees progress regardless of whether some threads are delayed or even killed and regardless of scheduling policies. This paper presents a completely lock-free Memory allocator. It uses only widely-available operating system support and hardware atomic instructions. It offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to deadlock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. Also, by leveraging some high-level structures from Hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing. In addition, our allocator allows finer concurrency and much lower latency than Hoard. We use PowerPC shared Memory multiprocessor systems to compare the performance of our allocator with the default AIX 5.1 libc malloc, and two widely-used multithread allocators, Hoard and Ptmalloc. Our allocator outperforms the other allocators in virtually all cases and often by substantial margins, under various levels of parallelism and Allocation patterns. Furthermore, our allocator also offers the lowest contention-free latency among the allocators by significant margins.
-
PLDI - Scalable lock-free Dynamic Memory Allocation
Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation - PLDI '04, 2004Co-Authors: Maged M MichaelAbstract:Dynamic Memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, and programming flexibility. A lock-free Memory allocator guarantees progress regardless of whether some threads are delayed or even killed and regardless of scheduling policies. This paper presents a completely lock-free Memory allocator. It uses only widely-available operating system support and hardware atomic instructions. It offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to deadlock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. Also, by leveraging some high-level structures from Hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing. In addition, our allocator allows finer concurrency and much lower latency than Hoard. We use PowerPC shared Memory multiprocessor systems to compare the performance of our allocator with the default AIX 5.1 libc malloc, and two widely-used multithread allocators, Hoard and Ptmalloc. Our allocator outperforms the other allocators in virtually all cases and often by substantial margins, under various levels of parallelism and Allocation patterns. Furthermore, our allocator also offers the lowest contention-free latency among the allocators by significant margins.
Rajeev Barua - One of the best experts on this subject based on the ideXlab platform.
-
compiler decided Dynamic Memory Allocation for scratch pad based embedded systems
Compilers Architecture and Synthesis for Embedded Systems, 2003Co-Authors: Sumesh Udayakumaran, Rajeev BaruaAbstract:This paper presents a highly predictable, low overhead and yet Dynamic, Memory Allocation strategy for embedded systems with scratch-pad Memory. A scratch-pad is a fast compiler-managed SRAM Memory that replaces the hardware-managed cache. It is motivated by its better real-time guarantees vs cache and by its significantly lower overheads in energy consumption, area and overall runtime, even with a simple Allocation scheme [4].Existing scratch-pad Allocation methods are of two types. First, software-caching schemes emulate the workings of a hardware cache in software. Instructions are inserted before each load/store to check the software-maintained cache tags. Such methods incur large overheads in runtime, code size, energy consumption and SRAM space for tags and deliver poor real-time guarantees just like hardware caches. A second category of algorithms partitionsm variables at compile-time into the two banks. For example, our previous work in [3] derives a provably optimal static Allocation for global and stack variables and achieves a speedup over all earlier methods. However, a drawback of such static Allocation schemes is that they do not account for Dynamic program behavior. It is easy to see why a data Allocation that never changes at runtime cannot achieve the full locality benefits of a cache.In this paper we present a Dynamic Allocation method for global and stack data that for the first time, (i) accounts for changing program requirements at runtime (ii) has no software-caching tags (iii) requires no run-time checks (iv) has extremely low overheads, and (v) yields 100% predictable Memory access times. In this method data that is about to be accessed frequently is copied into the SRAM using compiler-inserted code at fixed and infrequent points in the program. Earlier data is evicted if necessary. When compared to a provably optimal static Allocation our results show runtime reductions ranging from 11% to 38%, averaging 31.2%, using no additional hardware support. With hardware support for pseudo-DMA and full DMA, which is already provided in some commercial systems, the runtime reductions increase to 33.4% and 34.2% respectively.
-
CASES - Compiler-decided Dynamic Memory Allocation for scratch-pad based embedded systems
Proceedings of the international conference on Compilers architectures and synthesis for embedded systems - CASES '03, 2003Co-Authors: Sumesh Udayakumaran, Rajeev BaruaAbstract:This paper presents a highly predictable, low overhead and yet Dynamic, Memory Allocation strategy for embedded systems with scratch-pad Memory. A scratch-pad is a fast compiler-managed SRAM Memory that replaces the hardware-managed cache. It is motivated by its better real-time guarantees vs cache and by its significantly lower overheads in energy consumption, area and overall runtime, even with a simple Allocation scheme [4].Existing scratch-pad Allocation methods are of two types. First, software-caching schemes emulate the workings of a hardware cache in software. Instructions are inserted before each load/store to check the software-maintained cache tags. Such methods incur large overheads in runtime, code size, energy consumption and SRAM space for tags and deliver poor real-time guarantees just like hardware caches. A second category of algorithms partitionsm variables at compile-time into the two banks. For example, our previous work in [3] derives a provably optimal static Allocation for global and stack variables and achieves a speedup over all earlier methods. However, a drawback of such static Allocation schemes is that they do not account for Dynamic program behavior. It is easy to see why a data Allocation that never changes at runtime cannot achieve the full locality benefits of a cache.In this paper we present a Dynamic Allocation method for global and stack data that for the first time, (i) accounts for changing program requirements at runtime (ii) has no software-caching tags (iii) requires no run-time checks (iv) has extremely low overheads, and (v) yields 100% predictable Memory access times. In this method data that is about to be accessed frequently is copied into the SRAM using compiler-inserted code at fixed and infrequent points in the program. Earlier data is evicted if necessary. When compared to a provably optimal static Allocation our results show runtime reductions ranging from 11% to 38%, averaging 31.2%, using no additional hardware support. With hardware support for pseudo-DMA and full DMA, which is already provided in some commercial systems, the runtime reductions increase to 33.4% and 34.2% respectively.
Marc Sevaux - One of the best experts on this subject based on the ideXlab platform.
-
A multiple neighborhood search for Dynamic Memory Allocation in embedded systems
Journal of Heuristics, 2015Co-Authors: Maria Soto, André Rossi, Marc SevauxAbstract:Memory Allocation has a significant impact on power consumption in embedded systems. We address the Dynamic Memory Allocation problem, in which Memory requirements may change at each time interval. This problem has previously been addressed using integer linear programming and iterative approaches which build a solution interval by interval taking into account the requirements of partial time intervals. A GRASP that builds a solution for all time intervals has been proposed as a global approach. Due to the complexity of this problem, the GRASP algorithm solution quality decreases for larger instances. In order to overcome this drawback, we propose a multiple neighborhood search hybridized with a Tabu Search and enhanced by complex ejection chains. The proposed approach outperforms all previously developed methods devised for the Dynamic Memory Allocation problem.
-
Solving Dynamic Memory Allocation problems in embedded systems with parallel variable neighborhood search strategies
Electronic Notes in Discrete Mathematics, 2015Co-Authors: Jesús Sánchez-oro, André Rossi, Marc Sevaux, Rafael Marti, Abraham DuarteAbstract:Embedded systems have become an essential part of our lives, thanks to their evolution in the recent years, but the main drawback is their power consumption. This paper is focused on improving the Memory Allocation of embedded systems to reduce their power consumption. We propose a parallel variable neighborhood search algorithm for the Dynamic Memory Allocation problem, and compare it with the state of the art. Computational results and statistical tests applied show that the proposed algorithm produces significantly better outcomes than the previous algorithm in shorter computing time.
-
GRASP with ejection chains for the Dynamic Memory Allocation in embedded systems
Soft Computing, 2014Co-Authors: Marc Sevaux, Maria Soto, André Rossi, Abraham Duarte, Rafael MartiAbstract:In the design of electronic embedded systems, the Allocation of data structures to Memory banks is a main challenge faced by designers. Indeed, if this optimization problem is solved correctly, a great improvement in terms of efficiency can be obtained. In this paper, we consider the Dynamic Memory Allocation problem, where data structures have to be assigned to Memory banks in different time periods during the execution of the application. We propose a GRASP to obtain high quality solutions in short computational time, as required in this type of problem. Moreover, we also explore the adaptation of the ejection chain methodology, originally proposed in the context of tabu search, for improved outcomes. Our experiments with real and randomly generated instances show the superiority of the proposed methods compared to the state-of-the-art method.
-
Iterative approaches for a Dynamic Memory Allocation problem in embedded systems
European Journal of Operational Research, 2013Co-Authors: Maria Soto, André Rossi, Marc SevauxAbstract:Memory Allocation has a significant impact on energy consumption in embedded systems. In this paper, we are interested in Dynamic Memory Allocation for embedded systems with a special emphasis on time performance. We propose two mid-term iterative approaches which are compared with existing long-term and short-term approaches, and with an ILP formulation as well. These approaches rely on solving a static version of the Allocation problem and they take advantage of previous works for addressing the static problem. A statistic analysis is carried out for showing that the mid-term approach is the best one in terms of solution quality.
-
two iterative metaheuristic approaches to Dynamic Memory Allocation for embedded systems
European conference on Evolutionary Computation in Combinatorial Optimization, 2011Co-Authors: Maria Soto, André Rossi, Marc SevauxAbstract:Electronic embedded systems designers aim at finding a tradeoff between cost and power consumption. As cache Memory management has been shown to have a significant impact on power consumption, this paper addresses Dynamic Memory Allocation for embedded systems with a special emphasis on time performance. In this work, time is split into time intervals, into which the application to be implemented by the embedded system requires accessing to data structures. The proposed iterative metaheuristics aim at determining which data structure should be stored in cache Memory at each time interval in order to minimize reAllocation and conflict costs. These approaches take advantage of metaheuristics previously designed for a static Memory Allocation problem.
Y. Hasan - One of the best experts on this subject based on the ideXlab platform.
-
Upper Bounds for Dynamic Memory Allocation
IEEE Transactions on Computers, 2010Co-Authors: Y. Hasan, J.m. Chang, Wei-mei Chen, B.m. GharaibehAbstract:In this paper, we study the upper bounds of Memory storage for two different allocators. In the first case, we consider a general allocator that can allocate Memory blocks anywhere in the available heap space. In the second case, a more economical allocator constrained by the address-ordered first-fit Allocation policy is considered. We derive the upper bound of Memory usage for all allocators and present a systematic approach to search for Allocation/deAllocation patterns that might lead to the largest fragmentation. These results are beneficial in embedded systems where Memory usage must be reduced and predictable because of lack of swapping facility. They are also useful in other types of computing systems.
-
evaluation of a high performance object reuse Dynamic Memory Allocation policy for c programs
IEEE International Conference on High Performance Computing Data and Analytics, 2000Co-Authors: Woo Hyong Lee, J.m. Chang, Y. HasanAbstract:The importance of Dynamic Memory management has increased significantly as there is a growing number of developments in object-oriented programs. Many studies show that Dynamic Memory management is one of the most expensive components in many software systems. In C++ programs especially, it tends to have prolific object creation and deletion. These objects tend to have short life-spans. This paper presents a Dynamic Memory Allocation strategy to reuse these objects to speed up the object management. This object reuse scheme is implemented through the overloading C++ operators, new and delete. The C++ Allocation patterns are studied thoroughly in this paper. Over 90% of objects are not bigger than 512 bytes and allocated prolifically. The proposed scheme is made feasible by reuse of these small objects. Our Allocation scheme is simple and fast because it requires no splitting and no coalescing, and reduces the number of malloc() calls. It maintains its own free-list which is used for object reuse. The experimented results, based on the proposed Allocation scheme, show that Allocation speed is increased up to four times compared to other well-known algorithms. Our scheme is purely source-code oriented and built on top of malloc. Therefore, this approach is portable for application to existing code and safe to use with different mallocs.
-
Evaluation of a high-performance object reuse Dynamic Memory Allocation policy for C++ programs
Proceedings Fourth International Conference Exhibition on High Performance Computing in the Asia-Pacific Region, 2000Co-Authors: Woo Hyong Lee, J.m. Chang, Y. HasanAbstract:The importance of Dynamic Memory management has increased significantly as there is a growing number of developments in object-oriented programs. Many studies show that Dynamic Memory management is one of the most expensive components in many software systems. In C++ programs especially, it tends to have prolific object creation and deletion. These objects tend to have short life-spans. This paper presents a Dynamic Memory Allocation strategy to reuse these objects to speed up the object management. This object reuse scheme is implemented through the overloading C++ operators, new and delete. The C++ Allocation patterns are studied thoroughly in this paper. Over 90% of objects are not bigger than 512 bytes and allocated prolifically. The proposed scheme is made feasible by reuse of these small objects. Our Allocation scheme is simple and fast because it requires no splitting and no coalescing, and reduces the number of malloc() calls. It maintains its own free-list which is used for object reuse. The experimented results, based on the proposed Allocation scheme, show that Allocation speed is increased up to four times compared to other well-known algorithms. Our scheme is purely source-code oriented and built on top of malloc. Therefore, this approach is portable for application to existing code and safe to use with different mallocs.
Isabelle Puaut - One of the best experts on this subject based on the ideXlab platform.
-
Real-time performance of Dynamic Memory Allocation algorithms
Proceedings 14th Euromicro Conference on Real-Time Systems. Euromicro RTS 2002, 2002Co-Authors: Isabelle PuautAbstract:Dynamic Memory management is an important aspect of modern software engineering techniques. However developers of real-time systems avoid using it because they fear that the worst-case execution time of the Dynamic Memory Allocation routines is not bounded or is bounded with an excessively large bound. The degree to which this concern is valid is quantified in this paper by giving detailed average and worst-case measurements of the timing performance of a comprehensive panel of Dynamic Memory allocators. For each allocator we compare its worst-case behavior obtained analytically with the worst timing behavior observed by executing real and synthetic workloads, and with its average timing performance. The results provide a guideline to developers of real-time systems to choose whether to use Dynamic Memory management or not, and which Dynamic Allocation algorithm should be preferred from the viewpoint of predictability.
-
ECRTS - Real-time performance of Dynamic Memory Allocation algorithms
Proceedings 14th Euromicro Conference on Real-Time Systems. Euromicro RTS 2002, 1Co-Authors: Isabelle PuautAbstract:Dynamic Memory management is an important aspect of modern software engineering techniques. However developers of real-time systems avoid using it because they fear that the worst-case execution time of the Dynamic Memory Allocation routines is not bounded or is bounded with an excessively large bound. The degree to which this concern is valid is quantified in this paper by giving detailed average and worst-case measurements of the timing performance of a comprehensive panel of Dynamic Memory allocators. For each allocator we compare its worst-case behavior obtained analytically with the worst timing behavior observed by executing real and synthetic workloads, and with its average timing performance. The results provide a guideline to developers of real-time systems to choose whether to use Dynamic Memory management or not, and which Dynamic Allocation algorithm should be preferred from the viewpoint of predictability.
