Task Scheduling And Data Allocation For Systems With Non-volatile Memory

Applications that run in the embedded systems normally should be finished within a timing constraint in energy-efficient fashion. In addition to computation, memory accesses in these embedded systems account for a large percentage of time and energy. Therefore, time-efficient and energy-efficient on-chip memories and corresponding optimization techniques are desirable for embedded systems. In recent years, emerging Non-Volatile Memories(NVMs) have captured the attention of academia and semiconductor industry, and become the promising replacement of SRAM to settle the energy and density problem of on-chip memory. NVMs have many attractive characteristics such as ultra low leakage power, fast read access, high-density, and non-volatility. However, NVMs also have their own drawbacks: high dynamic energy consumption, long write latency, and limited endurance. In this thesis, we propose task scheduling and data allocation techniques for NVM based memroy in embedded systems. The main contributions of this thesis include:1) We propose task scheduling and data allocation techniques for Domain Wall Memory(DWM) based memory for embedded systems. First, we propose a DWM based memory architecture model. In order to achieve area efficiency, we first adopt pure macro-cell DWM to build the SPM. To improve the performance of macro-cell DWM based SPM, we propose an integer non-linear programming(INLP) formulation to achieve the minimum number of shift through memory access instructions scheduling and data placement. Since INLP takes exponential time to finish, we propose a polynomial-time solution, the Instructions Group Schedule(IGS) algorithm. However, the time constraint of applications that run in a system equipped with macro-cell DWM based SPM may not be satisfied even though the number of shift operations is minimal. In such cases, it is necessary to adopt an SPM which consists of both micro-cell DWM and macro-cell DWM. The Longest Move Reduce(LMR) algorithm is then proposed to find a configuration of different DWM memory cells that can satisfy the time constraint with minimal area size.2) We propose data allocation techniques for multiple types of memoris in embedded systems. We model data allocation problem on multiple types of memories by probabilities. We propose the Access Frequency with Probability(AFP) model to represent data access frequencies with probabilities. For solving the data allocation problem with probabilities, we propose a dynamic programming algorithm, the Optimal Data Allocation with Probability(ODAP) algorithm. We also propose a polynomial-time algorithm, the Maximum Cost-Saving(MCS) algorithm. ODAP algorithm employs dynamic programming strategy to produce a set of feasible data allocation solutions which generates the minimum access cost guaranteed by a given probability. MCS algorithm is a near-optimal algorithm which can find near-optimal data allocation solutions quickly. To improve the performance of ODAP algorithm and MCS algorithm, we also propose Redundant Removal(R_R) algorithm.3) We propose task scheduling and data allocation techniques to improve the performance of multi-core systems with multi-port memory. We propose an Integer Linear Programming(ILP) formulation that determines task scheduling and data allocation simultaneously to get an optimal schedule with minimum length. ILP formulation can guarantee optimal results. However, ILP takes exponential time to finish, which is not acceptable for large inputs. In order to solve large inputs efficiently, we propose a polynomial-time near-optimal heuristic algorithm, which consists of three phases. First, we propose Task Assignment with Remote Access Reduced(TARAR)algorithm to determine task assignment by exploring opportunity of parallelism of data accesses and tasks. The first phase will generate a core-to-data matrix which describes the access frequency of each core to each data. In the second phase, according to the core-to-data matrix obtained from task assignment, we propose Minimum Memory Access Cost(MMAC) algorithm to allocate each data to the core which minimizes the total memory access cost. In the third phase, we propose As Soon As Possible(ASAP)algorithm to determine the start time of tasks and data accesses operations.According to the experimental results, our techniques can improve the performance of systems and reduce their energy consumption.