Efficient full-state quantum circuit simulations are useful tools for the design of quantum algorithms. Multi-node distributed systems are commonly employed as such simulations require a large amount of computation power and memory space. In distributed systems, communication overhead can be the performance bottleneck. This paper presents a distributed simulation framework called QuanTrans. A quantum circuit is composed of many levels of quantum gates. The simulation is conducted level by level. For circuits with particular structures, it employs a hybrid simulation approach to replace intermediate multi-level communications with one level of final merge operation, whose communication volume is comparable to that of one level of simulation in previous work. A circuit without such structures is sliced to find applicable sub-circuits with a single or multiple consecutive level(s). One level of communication is required for each sub-circuit, so we further propose a polynomial-time optimal circuit slicing algorithm. It can transform any circuit such that the number of sliced sub-circuits is the minimum after transformation. Experimental results show that QuanTrans can effectively reduce communication time and simulation time.

Modular quantum architectures have emerged as a promising solution for scalable quantum computing systems. Executing circuits in such distributed systems necessitates non-local operations between modules, incurring significant communication overhead. In this work, an optimized quantum circuit mapping technique called DQTetris is proposed to reduce inter-module communications. DQTetris employs a hierarchical framework that first seeks a global communication-free qubit mapping assignment under module capacity constraints. If infeasible, it searches for subcircuits with local communication-free qubit assignments via layer-wise gate pruning. Executing adjacent subcircuits with different qubit assignments incurs inter-module data teleportation. DQTetris minimizes these overheads by reducing qubit reassignment events through optimal circuit segmentation, qubit assignment selection, and adaptive gate teleportation. Experiments show that compared with existing methods, DQTetris can achieve average reductions in communication costs ranging from 28% to 75% across various benchmarks.

Mobile devices have become ubiquitous in daily life. In contrast to traditional servers, mobile devices suffer from limited memory resources, leading to a significant degradation in the user experience. This paper demonstrates that the primary cause of memory consumption lies in anonymous pages associated with application heaps. Existing schemes are ineffective in deduplicating these pages due to the limited occurrence of the same anonymous pages. This paper presents Sparrow, a similar-page aware deduplication solution for mobile systems. Sparrow shows that memory pages still have the potential to deduplicate, even though the same pages are rare. An interesting observation inspires this, that is, a high number of pages having the partially-same contents. We have implemented Sparrow on real-life smartphones. Experimental results indicate that 30.45% more space can be saved with Sparrow.

With the development of quantum computing, quantum processor demonstrates the potential supremacy in specific applications, such as Grover's database search and popular quantum neural networks (QNNs). For better calibrating the quantum algorithms and machines, quantum circuit simulation on classical computers becomes crucial. However, as the number of quantum bits (qubits) increases, the memory requirement grows exponentially. In order to reduce memory usage and accelerate simulation, we propose a multi-level optimization, namely Mera, by exploring memory and computation redundancy. First, for a large number of sparse quantum gates, we propose two compressed structures for low-level full-state simulation. The corresponding gate operations are designed for practical implementations, which are relieved from the longtime compression and decompression. Second, for the dense Hadamard gate, which is definitely used to construct the superposition, we design a customized structure for significant memory saving as a regularity-oriented simulation. Meanwhile, an ondemand amplitude updating process is optimized for execution acceleration. Experiments show that our compressed structures increase the number of qubits from 17 to 35, and achieve up to$6.9 \times$acceleration for QNN.

Racetrack memory (RTM), which consists of multiple domain block clusters (DBC) and access ports, is a novel non-volatile memory and has potential as scratchpad memory (SPM) in embedded devices due to its high density and low access latency. However, too many shift operations decrease the performance of RTM and cause unpredictable performance. In this paper, we propose three schemes to optimize the performance of RTM from different aspects, including intra-DBC, inter-DBC, and hybrid SPM with SRAM and RTM. Firstly, a balanced group-based data placement method for the data layout inside one DBC is proposed to reduce shifts. Second, a grouping method for the data allocation among DBCs is proposed. It helps with the shift reduction while using fewer DBCs by using one DBC as multiple DBCs. Finally, we use SRAM to further help the cost reduction, and a cost evaluation metric is proposed to assist the shrinking method which determines the data allocation for hybrid SPM with SRAM and RTM. Experiments show that the proposed schemes can significantly improve the performance of pure RTM and hybrid SPM while using fewer DBCs.

Nonvolatile memory (NVM) has the potential as the medium for scratchpad memory (SPM) in embedded devices. Racetrack memory (RM), in particular, is a developing memory technology that possesses high density and read latency comparable to SRAM. The RM’s access operations, however, are based on shift operations. Multiple shift operations will lead to long access latency and high energy. In this article, SRAM is borrowed to help the shifts reduction. Thus, a novel hybrid SRAM+RM SPM is presented to make use of SRAM’s random access and RM’s high density. But, there are some challenges to the proposed architecture: 1) the large capacity of SRAM is not available due to its low density and 2) due to the drawbacks of RM mentioned above, data that are randomly accessed are not expected to be stored on RM. Therefore, a data placement scheme and an instruction scheduling strategy are presented for the proposed architecture. First, an access instruction scheduling strategy is introduced to obtain a relatively sequential access sequence to help with the shifts and SRAM size reduction; second, to help with data placement, a metric for representing the data access cost is proposed; third, a data placement strategy based on the metric is proposed; and finally, a solution for decreasing SRAM size is suggested to maximize the capacity of SPM (or minimize the size of SPM). Experiments show that the suggested scheme can significantly improve the performance of the hybrid SPM while also reducing the shifts on RM with minimal SRAM.

Along with the progress of AI democratization, machine learning (ML) has been successfully applied to edge applications, such as smart phones and automated driving. Nowadays, more applications require ML on tiny devices with extremely limited resources, like implantable cardioverter de-fibrillator (ICD), which is known as TinyML. Unlike ML on the edge, TinyML with a limited energy supply has higher demands on low-power execution. Stochastic computing (SC) using bitstreams for data representation is promising for TinyML since it can perform the fundamental ML operations using simple logical gates, instead of the complicated binary adder and multiplier. However, SC commonly suffers from low accuracy for ML tasks due to low data precision and inaccuracy of arithmetic units. Increasing the length of the bitstream in the existing works can mitigate the precision issue but incur higher latency. In this work, we propose a novel SC architecture, namely Block-based Stochastic Computing (BSC). BSC divides inputs into blocks, such that the latency can be reduced by exploiting high data parallelism. Moreover, optimized arithmetic units and output revision (OUR) scheme are proposed to improve accuracy. On top of it, a global optimization approach is devised to determine the number of blocks, which can make a better latency-power trade-off. Experimental results show that BSC can outperform the existing designs in achieving over 10% higher accuracy on ML tasks and over$6\times$power reduction.

Non-volatile memory (NVM) is expected to be the second level memory (named remote memory) in two-level memory hierarchy in the future. However, NVM has the limited write endurance, thus it is vital to reduce the number of write operations on NVM. Meanwhile, in two-level memory hierarchy, prefetch is widely used for fetching certain data before it is actually required, to hide the remote memory access latency. In general, large-scale nested loop is the performance bottleneck in one program due to the write operations on NVM caused by the first level memory (named local memory) miss and data reuse. Loop tiling is the key technique for grouping iterations so as to reduce the communication with remote memory used in compiler. In this paper, we propose a new loop tiling approach for minimizing the write operations on NVMs and completely hiding the NVM access latency. Specifically, we introduce a series of theorems to help loop tiling. Then, a legal tile shape and an optimal tile size selection strategy is proposed according to data dependency and local memory capacity. Furthermore, we propose a pipeline scheduling policy to completely hide the remote memory latency. Extensive experiments show that the proposed techniques can reduce write operations on NVMs by 95.1% on average, and NVM latency can be completely hidden.

For a real-time task-intensive systems, the fairness of task execution in dynamic scheduling is an important research area. However, many exist scheduling algorithms are unable to guarantee that tasks can be completed by the deadline and executed with a fair priority. In this paper, we proposed an efficient Multi-DAG real-time scheduling algorithm, HSDFW, which employs a fair priority calculation method to enable tasks with different real-time levels can be completed by the deadline, and a rejection policy to improve the performance of schedule. We proposed an INLP model and an evaluation simulator to verify the efficiency of HSDFW algorithm. The evaluation results show that our proposed algorithm has excellent performance in terms of average scheduling length and resource utilization.

This work found that the state-of-the-art multi-streamed SSDs are inefficiently used due to two issues. First, the write cache inside SSDs is not aware of data from different streams, which induce conflict among streams. Second, the current stream identification methods are not accurate, which should be optimized inside SSDs. This work proposed a novel write cache scheme to efficiently utilize and optimize the multiple streams. First, an inter-stream aware cache partitioning scheme is proposed to manage the data from different streams. Second, an intra-stream based active cache evicting scheme is proposed to evict data to block with more invalid pages in priority. Experiment results show that the proposed scheme significantly reduces the write amplification (WAF) of multi-streamed SSDs by up to 28% with negligible cost.

A pruning-based AutoML framework for run-time reconfigurability, namely RT3, is proposed in this work. This enables Transformer-based large Natural Language Processing (NLP) models to be efficiently executed on resource-constrained mobile devices and reconfigured (i.e., switching models for dynamic hardware conditions) at run-time. Such reconfigurability is the key to save energy for battery-powered mobile devices, which widely use dynamic voltage and frequency scaling (DVFS) technique for hardware reconfiguration to prolong battery life. In this work, we creatively explore a hybrid block-structured pruning (BP) and pattern pruning (PP) for Transformer-based models and first attempt to combine hardware and software reconfiguration to maximally save energy for battery-powered mobile devices. Specifically, RT3integrates two-level optimizations: First, it utilizes an efficient BP as the first-step compression for resource-constrained mobile devices; then, RT3heuristically generates a shrunken search space based on the first level optimization and searches multiple pattern sets with diverse sparsity for PP via reinforcement learning to support lightweight software reconfiguration, which corresponds to available frequency levels of DVFS (i.e., hardware reconfiguration). At run-time, RT3can switch the lightweight pattern sets within 45ms to guarantee the required real-time constraint at different frequency levels. Results further show that RT3can prolong battery life over $ 4\times$ improvement with less than 1% accuracy loss for Transformer and 1.5% score decrease for DistilBERT.

Recently, Transformers gradually gain popularity and perform outstanding for many Natural Language Processing (NLP) tasks. However, Transformers suffer from heavy computation and memory footprint, making it difficult to deploy on embedded devices. The field-programmable gate array (FPGA) is widely used to accelerate deep learning algorithms for its advantages. However, the trained Transformer models are too large to accommodate to an FPGA fabric. To accommodate Transformer onto FPGA and achieve efficient execution, we propose an acceleration framework coupling the balanced model compression at the algorithm level and FPGA-implementation optimization at the hardware level. At algorithm level, we adopt a block-balanced pruning and propose an efficient sparse matrix storage format for this pruning technique, named Compressed Block Row (CBR). At the hardware level, we design an accelerator for sparse model. And we also abstract a performance analytic model to evaluate the performance of accelerator. Experiments show that our CBR format perform better than general formats and can significantly save storage space. And our accelerator can achieve $38\times$ and $1.93\times$ speedup compared to other works on CPU and GPU respectively.

Currently, most of the Flash-based storage systems reduce the performance gap between the main memory and storage by data prefetching. However, conventional prefetching techniques perform well on hard disk drives but have limited effectiveness and efficiency on Flash. It is because the complicate data access patterns in modern systems have not been well considered. In this paper, we propose SFP, a smart file-aware prefetching scheme for Flash-based storage systems. SFP demonstrates that prefetching accuracy and efficiency can be improved comprehensively in a file-aware approach. Furthermore, three schemes are proposed: file access pattern learning, dynamic window-based file prefetching, and learning model size optimization. Experiments on the real server show that SFP reduces the access latency by up to 40% compared with the state-of-the-art with low memory and computation cost.

Racetrack memory (RM) has high access performance comparable to SRAM. It is a kind of non-volatile memory (NVM), which consists of data block clusters (DBCs) and access ports. However, data accessing on RM is based on shift operations, which will decrease the performance of RM. This paper proposes techniques by using SRAM to reduce the shifts and improve the accessing performance of RM. The key idea is to place randomly accessed data on SRAM ahead of time to relax the data placement on RM. First, a greedy scheduling strategy is proposed to reduce the requirement of SRAM. Second, to further reduce shifts, data with similar association degree are grouped and allocated to each DBC. Experimental results show that the proposed techniques reduce the shifts by 72.3% with only 256-byte SRAM compared to pure RM.

State-of-the-art Transformer-based models, with gigantic parameters, are difficult to be accommodated on resource constrained embedded devices. Moreover, with the development of technology, more and more embedded devices are available to run a Transformer model. For a Transformer model with different constraints (tight or loose), it can be deployed onto devices with different computing power. However, in previous work, designers did not choose the best device among multiple devices. Instead, they just used an existing device to deploy model, which was not necessarily the best fit and may lead to underutilization of resources. To address the deployment challenge of Transformer and the problem to select the best device, we propose an algorithm$\leftrightarrows$hardware closed-loop acceleration framework. Given a dataset, a model, latency constraint LC and accuracy constraint AC, our framework can provide a best device satisfying both constraints. In order to generate a compressed model with high sparsity ratio, we propose a novel pruning technique, hierarchical pruning (HP). We optimize the sparse matrix storage format for HP matrix to further reduce memory usage for FPGA implementation. We design a accelerator that takes advantage of HP to solve the problem of concurrent random access. Experiments on Transformer and TinyBert model show that our framework can find different devices for various LC and AC, covering from low-end devices to high-end devices. Our HP can achieve higher sparsity ratio and is more flexible than other sparsity pattern. Our framework can achieve 37 x, 1.9 x, 1.7x speedup compared to CPU, GPU and FPGA, respectively.

Existing persistent memory file systems exploit the fast, byte-addressable persistent memory (PM) to boost storage performance but ignore the limited endurance of PM. Particularly, the PM storing the inode section is extremely vulnerable for the inodes are most frequently updated, fixed on a location throughout lifetime, and require immediate persistency. The huge endurance variation of persistent memory domains caused by process variation makes things even worse. In this article, we propose a process variation aware wear leveling mechanism called Contour for the inode section of persistent memory file system. Contour first enables the movement of inodes by virtualizing the inodes with a deflection table. Then, Contour adopts cross-domain migration algorithm and intra-domain migration algorithm to balance the writes across and within the memory domains. We implement the proposed Contour mechanism in Linux kernel 4.4.30 based on a real persistent memory file system, SIMFS. We use standard benchmarks, including Filebench, MySQL, and FIO, to evaluate Contour. Extensive experimental results show Contour can improve the wear ratios of pages 417.8× and 4.5× over the original SIMFS and PCV, the state-of-the-art inode wear-leveling algorithm, respectively. Meanwhile, the average performance overhead and wear overhead of Contour are 0.87 and 0.034 percent in application-level workloads, respectively.

Efficiently accessing remote file data remains a challenging problem for data processing systems. Development of technologies in non-volatile dual in-line memory modules (NVDIMMs), in-memory file systems, and RDMA networks provide new opportunities towards solving the problem of remote data access. A general understanding about NVDIMMs, such as Intel Optane DC Persistent Memory (DCPM), is that they expand main memory capacity with a cost of multiple times lower performance than DRAM. With an in-depth exploration presented in this paper, however, we show an interesting finding that the potential of NVDIMMs for high-performance, remote in-memory accesses can be revealed through careful design. We explore multiple architectural structures for accessing remote NVDIMMs in a real system using Optane DCPM, and compare the performance of various structures. Experiments are conducted to show significant performance gaps among different ways of using NVDIMMs as memory address space accessible through RDMA interface. Furthermore, we design and implement a prototype of user-level, in-memory file system, RIMFS, in the device DAX mode on Optane DCPM. By comparing against the DAX-supported Linux file system, Ext4-DAX, we show that the performance of remote reads on RIMFS over RDMA is 11.44 higher than that on a remote Ext4-DAX on average. The experimental results also show that the performance of remote accesses on RIMFS is maintained on a heavily loaded data server with CPU utilization as high as 90%, while the performance of remote reads on Ext4-DAX is significantly reduced by 49.3%, and the performance of local reads on Ext4-DAX is even more significantly reduced by 90.1%. The performance comparisons of writes exhibit the same trends.

Existing persistent memory file systems usually store inodes in fixed locations, which ignores the external and internal imbalanced wears of inodes on the persistent memory (PM). Therefore, the PM for storing inodes can be easily damaged. Existing solutions achieve low accuracy of wear-leveling with high-overhead data migrations. In this paper, we propose a Lightweight and Multi-grained Wear-leveling Mechanism, called LMWM, to solve these problems. We implement the proposed LMWM in Linux kernel based on NOVA, a typical persistent memory file system. Compared with MARCH, the state-of-theart wear-leveling mechanism for inode table, experimental results show that LMWM can improve 2.5× lifetime of PM and 1.12× performance, respectively.

Existing persistent memory file systems can significantly improve the performance by utilizing the advantages of emerging Persistent Memories (PMs). Especially, they can employ superpages (e.g., 2MB a page) of PMs to alleviate the overhead of locating file data and reduce TLB misses. Unfortunately, superpage also induces two critical problems. First, the data consistency of file systems using superpages causes severe write amplification during overwrite of file data. Second, existing management of superpages may lead to large waste of PM space. In this paper, we propose a Virtual Superpage Mechanism (VSM) to solve the problems by taking advantages of virtual address space. On one hand, VSM adopts multi-grained copy-on-write mechanism to reduce the write amplification while ensuring data consistency. On the other hand, VSM presents zero-copy file data migration mechanism to eliminate the loss of space utilization efficiency caused by superpages. We implement the proposed VSM mechanism in Linux kernel based on PMFS. Compared with the original PMFS and NOVA, the experimental results show that VSM improves 36% and 14% on average for write and read performance, respectively. Meanwhile, VSM can achieve the same space utilization efficiency of file system that uses the normal 4KB pages to organize files.

State-of-the-art high density NAND flash memory has been recommended as read intensive storage device due to their excellent read performance. However, recent studies and reports show that the read latency of high density NAND flash memory is increasing. The reason comes from at least two aspects: First, high density flash generally adopts multiple bits per cell technique, where the access latency of the most significant bits is largely increased. Second, due to the reliability variation among these bits, the access latency of the most significant bits is further increased. We introduce RLV, a read performance optimization scheme is proposed to exploit the read latency variation among the multiple bits. The basic idea is that firstly identify the hotness of read data and then move them to the places with corresponding read latency. Our evaluation shows that RLV incurs negligible overhead, while improving read performance by 14% on average compared with state-of-the-arts.

To improve the performance of address translation in applications with large memory footprints, techniques, such as hugepages and HW coalescing, are proposed to increase the coverage of limited hardware translation entries by exploiting the contiguous memory allocation to lower Tanslation Lookaside Buffer (TLB) miss rate. Furthermore, Page Table Caches (PTCs) are proposed to store the upper-level page table entries to reduce the TLB miss handling latency. Both increasing TLB coverage and reducing TLB miss handling latency have proved to be effective in speeding up address translation, to a certain extent. Nevertheless, our preliminary studies suggest that the structural separation between TLBs and PTCs in existing computer systems makes these two methods less effective because they are exclusively used in TLBs and PTCs respectively. In particular, the separate structures cannot dynamically adjust their sizes according to the workloads, resulting in low resource utilization and inefficient address translation. To address these issues, we propose a unified structure, called Unified - Tp,which stores PTC and TLB entries together. Besides, Our modified LRU algorithm helps identify the cold TLB and PTC entries and dynamically adjust the numbers of TLB and PTC entries to adapt to different workloads. Furthermore, we introduce a scheme of parallel search when receiving memory access requests. Our experimental results show that Unified-TP can reduce the numbers of TLB misses by an average of 35.69 % and improve the performance by an average of 11.12% compared with separately structured TLBs and PTCs.

In this paper, a novel hybrid scratchpad memory (SPM) with SRAM and racetrack memory (RM) is proposed. The basic idea is to smartly place data on SPM by taking the advantages of these two memories. First, a metric is proposed to represent the access cost of data; Second, a data placement scheme is proposed based on the metric; Finally, to maximize the size of SPM, a scheme is further proposed to minimize the size of SRAM. Experimental results show that the proposed scheme reduces the shift operations of RM by 80.12% and reduces the cost of SPM by 80.72% with only 17.63% SRAM compared with a baseline SPM with pure RM.

We propose a novel hardware and software co-exploration framework for efficient neural architecture search (NAS). Different from existing hardware-aware NAS which assumes a fixed hardware design and explores theNAS spaceonly, our framework simultaneously explores both the architecture search space and thehardware design spaceto identify the best neural architecture and hardware pairs that maximize both test accuracy and hardware efficiency. Such a practice greatly opens up the design freedom and pushes forward the Pareto frontier between hardware efficiency and test accuracy for better design tradeoffs. The framework iteratively performs a two-level (fast and slow) exploration. Without lengthy training, the fast exploration can effectively fine-tune hyperparameters and prune inferior architectures in terms of hardware specifications, which significantly accelerates the NAS process. Then, the slow exploration trains candidates on a validation set and updates a controller using the reinforcement learning to maximize the expected accuracy together with the hardware efficiency. In this article, we demonstrate that the co-exploration framework can effectively expand the search space to incorporate models with high accuracy, and we theoretically show that the proposed two-level optimization can efficiently prune inferior solutions to better explore the search space. The experimental results on ImageNet show that the co-exploration NAS can find solutions with the same accuracy, 35.24% higher throughput, 54.05% higher energy efficiency, compared with the hardware-aware NAS.

Emerging non-volatile memories (NVMs) are promising main memory for their advanced characteristics. However, the low endurance of NVM cells makes them vulnerable to frequent fine-grained updates. This paper proposes a Wear-leveling Aware Fine-grained Allocator (WAFA) for NVM. WAFA divides pages into basic memory units to support fine-grained updates. WAFA allocates the basic memory units of a page in a rotational manner to distribute fine-grained updates evenly on memory cells. The fragmented basic memory units of each page caused by the memory allocation and deallocation operations are reorganized by reform operation. We implement WAFA in Linux kernel 4.4.4. Experimental results show that WAFA can reduce 81.1% and 40.1% of the total writes of pages over NVMalloc and nvm_alloc, the state-of-the-art wear-conscious allocator for NVM. Meanwhile, WAFA shows 48.6% and 42.3% performance improvement over NVMalloc and nvm_alloc, respectively.

A fundamental question lies in almost every application of deep neural networks: what is the optimal neural architecture given a specific data set? Recently, several Neural Architecture Search (NAS) frameworks have been developed that use reinforcement learning and evolutionary algorithm to search for the solution. However, most of them take a long time to find the optimal architecture due to the huge search space and the lengthy training process needed to evaluate each candidate. In addition, most of them aim at accuracy only and do not take into consideration the hardware that will be used to implement the architecture. This will potentially lead to excessive latencies beyond specifications, rendering the resulting architectures useless. To address both issues, in this paper we use Field Programmable Gate Arrays (FPGAs) as a vehicle to present a novel hardware-aware NAS framework, namely FNAS, which will provide an optimal neural architecture with latency guaranteed to meet the specification. In addition, with a performance abstraction model to analyze the latency of neural architectures without training, our framework can quickly prune architectures that do not satisfy the specification, leading to higher efficiency. Experimental results on common data set such as ImageNet show that in the cases where the state-of-the-art generates architectures with latencies 7.81× longer than the specification, those from FNAS can meet the specs with less than 1% accuracy loss. Moreover, FNAS also achieves up to 11.13× speedup for the search process. To the best of the authors' knowledge, this is the very first hardware aware NAS.

Real-time inference with low latency requirement has become increasingly important for numerous applications in both cloud computing and edge computing. The FPGA-based Deep Neural Network (DNN) accelerators have demonstrated the superior performance and energy efficiency over CPUs and GPUs; in addition, for real-time AI with low batch size, FPGA is expected to achieve further performance improvement over the general purpose computing platform. However, the performance gain of the single-FPGA design is hindered by the limited on-chip resource. In this paper, we leverage a cluster of FPGAs to fully exploit the parallelism in DNNs with the objective of obtaining super-linear performance. To achieve this goal, a novel design, "XFER", is proposed to deploy DNNs to FPGA cluster by splitting the DNN layer to multiple FPGAs and moving traffics from memory bus to inter-FPGA links. The resultant system can achieve both workload balance and traffic balance. As a case study, we implement Convolutional Neural Networks (CNNs) on ZCU102 FPGA boards. Evaluation results demonstrate that XFER on two FPGAs can achieve 3.48x speedup compared with state-of-the-art FPGA designs, achieving super-linear speedup.

Pipelining is a powerful technique to achieve high performance in computing systems. However, as computing platforms become large-scale and integrate with heterogeneous processing elements (PEs) (CPUs, GPUs, field-programmable gate arrays, etc.), it is difficult to employ a global clock to achieve synchronous pipelines. Therefore, self-timed (or asynchronous) pipelines are usually adopted. Nevertheless, due to their complex running behavior, the performance modeling and systematic optimizations for self-timed pipeline (STP) systems are more complicated than those for synchronous ones. This paper employs marked graph theory to model STPs and presents algorithms to detect performance bottlenecks. Based on the proposed model, we observe that the system performance can be improved by inserting buffers. Due to the limited memory resources on the PEs, it is critical to minimize the number of buffers for STPs while satisfying the required timing constraints. In this paper, we propose integer linear programming formulations to obtain the optimal solutions and devise efficient algorithms to obtain the near-optimal solutions. Experimental results show that the proposed algorithms can achieve 53.10% improvement in the maximum performance and 54.04% reduction in the number of buffers, compared with the technique for the slack matching problem.

Real-time Deep Neural Network (DNN) inference with low-latency requirement has become increasingly important for numerous applications in both cloud computing (e.g., Apple’s Siri) and edge computing (e.g., Google/Waymo’s driverless car). FPGA-based DNN accelerators have demonstrated both superior flexibility and performance; in addition, for real-time inference with low batch size, FPGA is expected to achieve further performance improvement. However, the performance gain from the single-FPGA design is obstructed by the limited on-chip resource. In this paper, we employ multiple FPGAs to cooperatively run DNNs with the objective of achieving super-linear speed-up against single-FPGA design. In implementing such systems, we found two barriers that hinder us from achieving the design goal: (1) the lack of a clear partition scheme for each DNN layer to fully exploit parallelism, and (2) the insufficient bandwidth between the off-chip memory and the accelerator due to the growing size of DNNs. To tackle these issues, we propose a general framework, “Super-LIP”, which can support different kinds of DNNs. In this paper, we take Convolutional Neural Network (CNN) as a vehicle to illustrate Super-LIP. We first formulate an accurate system-level model to support the exploration of best partition schemes. Then, we develop a novel design methodology to effectively alleviate the heavy loads on memory bandwidth by moving traffic from memory bus to inter-FPGA links. We implement Super-LIP based on ZCU102 FPGA boards. Results demonstrate that Super-LIP with 2 FPGAs can achieve 3.48× speedup, compared to the state-of-the-art single-FPGA design. What is more, as the number of FPGAs scales up, the system latency can be further reduced while maintaining high energy efficiency.

Existing persistent memory file systems achieve high-performance file accesses by exploiting advanced characteristics of persistent memories (PMs), such as PCM. However, they ignore the limited endurance of PMs. Particularly, the frequently updated inodes are stored on fixed locations throughout their lifetime, which can easily damage PM with common file operations. To address such issues, we propose a new mechanism, Virtualized Inode (VInode), for the wear leveling of inodes of persistent memory file systems. In VInode, we develop an algorithm called Pages as Communicating Vessels (PCV) to efficiently find and migrate the heavily written inodes. We implement VInode in SIMFS, a typical persistent memory file system. Experiments are conducted with well-known benchmarks. Compared with original SIMFS, experimental results show that VInode can reduce the maximum value and standard deviation of the write counts of pages to 1800x and 6200x lower, respectively.

This paper studies two basic problems in the design of high-performance and high-reliability heterogeneous systems: (1) what type of core to execute each task, and (2) where to place checkpoints in the execution of tasks. The implementation of checkpointing techniques on the novel persistent memory (e.g., 3D Xpoint memory) based heterogeneous systems faces a bundle of new problems. First, the assignments of tasks may greatly influence the execution time of the whole application. Therefore, with the same time constraint, the reliability of the resultant system can be significantly affected. Second, creating checkpoints will incur heavy writes on persistent memories and reduce the lifetime of devices. In this paper, we optimally construct reliable systems by assigning tasks to the most suitable cores and placing minimum number of checkpoints in the application, such that the resultant system can satisfy the time constraint in the presence of faults. We devise an efficient dynamic programming algorithm to obtain the optimal assignment and checkpoint placement. Experimental results demonstrate that, compared with existing approaches, our technique can achieve 44% reductions on the number of checkpoints on average.

More and more Non-Volatile Memories (NVM) have been widely applied to various embedded systems to build the heterogeneous memory architecture. However, the write-endurance of NVM remains a great challenge. Hence, we should take full consideration of the write-endurance of NVM when allocating data on heterogeneous memory architecture. There is an observation that, for most real workloads, about 10% of data account for 90% write operations. This brings us an opportunity to reduce the write wear of NVM through carefully allocating write-intensive data. In this paper, we explore the problem that how to find a balance between the system cost and write-endurance of NVM for data allocation on heterogeneous memory architecture. We propose a write-aware data allocation algorithm, WADA. WADA can not only greatly reduce the write wear of NVM, but also guarantee the near-optimal system cost. We also propose an integer linear programming (ILP) model to generate an optimal data allocation, which can obtain the minimum cost. The result of ILP can be used as a standard to evaluate the efficiency of other algorithms. Experiments show that WADA outperforms all the other algorithms on both system cost and write wear of NVM. Compared to previous algorithms, WADA can reduce up to 47.77% system cost and 60.89% write wear of NVM. Compared to ILP, WADA can achieve the near-optimal system cost within just 2% difference.

Index structures can significantly accelerate the data retrieval operations in data intensive systems, such as databases. Tree structures, such as B+-tree alike, are commonly employed as index structures; however, we found that the tree structure may not be appropriate for Non-Volatile Memory (NVM) in terms of the requirements for high-performance and high-endurance. This paper studies what is the best index structure for NVM-based systems and how to design such index structures. The design of an NVM-friendly index structure faces a lot of challenges. First, in order to prolong the lifetime of NVM, the write activities on NVM should be minimized. To this end, the index structure should be as simple as possible. The index proposed in this paper is based on the simplest data structure, i.e., linked list. Second, the simple structure brings challenges to achieve high-performance data retrieval operations. To overcome this challenge, we design a novel technique by explicitly building up a contiguous virtual address space on the linked list, such that efficient search algorithms can be performed. Third, we need to carefully consider data consistency issues in NVM-based systems, because the order of memory writes may be changed and the data content in NVM may be inconsistent due to write-back effects of CPU cache. This paper devises a novel indexing scheme, called “Virtual Linear Addressable Buckets” (VLAB). We implement VLAB in a storage engine and plug it into MySQL. Evaluations are conducted on an NVDIMM workstation using YCSB workloads and real-world traces. Results show that write activities of the state-of-the-art indexes are 6.98 times more than ours; meanwhile, VLAB achieves 2.53 times speedup.

Field programmable gate array (FPGA) has been one of the most popular platforms to implement convolutional neural networks (CNNs) due to its high performance and cost efficiency; however, limited by the on-chip resources, the existing single-FPGA architectures cannot fully exploit the parallelism in CNNs. In this paper, we explore heterogeneous FPGA-based designs to effectively leverage both task and data parallelism, such that the resultant system can achieve the minimum cost while satisfying timing constraints. In order to maximize the task parallelism, we investigate two critical problems: 1) buffer placement, where to place buffers to partition CNNs into pipeline stages and 2) task assignment, what type of FPGA to implement different CNN layers. We first formulate the system-level optimization problem with a mixed integer linear programming model. Then, we propose an efficient dynamic programming algorithm to obtain the optimal solutions. On top of that, we devise an efficient algorithm that exploits data parallelism within CNN layers to further improve cost efficiency. Evaluations on well-known CNNs demonstrate that the proposed techniques can obtain an average of 30.82% reduction in system cost under the same timing constraint, and an average of 1.5 times speedup in performance under the same cost budget, compared with the state-of-the-art techniques.

The emerging Phase Change Memory (PCM) is considered to be a promising candidate to replace DRAM as the next generation main memory due to its higher scalability and lower leakage power. However, the high write power consumption has become a major challenge in adopting PCM as main memory. In addition to the fact that writing to PCM cells requires high write current and voltage, current loss in the charge pumps also contributes a large percentage of high power consumption. The pumping efficiency of a PCM chip is a concave function of the write current. Leveraging the characteristics of the concave function, the overall pumping efficiency can be improved if the write current is uniform. In this article, we propose a peak-to-average (PTA) write scheme, which smooths the write current fluctuation by regrouping write units. In particular, we calculate the current requirements for each write unit by their values when they are evicted from the last level cache (LLC). When the write units are waiting in the memory controller, we regroup the write units by LLC-assisted PTA to reach the current-uniform goal. Experimental results show that LLC-assisted PTA achieved 13.4% of overall energy saving compared to the baseline.

Flash memory development through technology scaling and bit density has significant impact on the reliability of flash cells. Hence strong error correction code (ECC) schemes are highly recommended. With a strong error correction capability, low-density-parity code (LDPC) is now applied for the state-of-the-art flash memory. However, LDPC has long decoding latency when the raw bit error rates (RBER) are high. This is because it needs fine-grained soft sensing between states to iteratively decode the raw data. In this work, we propose a smart sensing level placement scheme to reduce the LDPC decoding latency. The basic idea for the placement scheme is motivated by two asymmetric error characteristics of flash memory: the asymmetric errors at different states, and the asymmetric errors caused by voltage left-shifts and right-shifts. With understanding of these two types of error characteristics, the sensing levels are smartly placed to achieve reduced sensing levels while maintaining the error correction capability of LDPC. Experiment analysis shows that the proposed scheme achieves significant performance improvement.

Pipelined heterogeneous multiprocessor system-on-chip (MPSoC) can provide high throughput for streaming applications. In the design of such systems, time performance and system cost are the most concerning issues. By analyzing runtime behaviors of benchmarks in real-world platforms, we find that execution times of tasks are not fixed but spread with probabilities. In terms of this feature, we model execution times of tasks as random variables. In this paper, we study how to design high-performance and low-cost MPSoC systems to execute a set of such tasks with data dependencies in a pipelined fashion. Our objective is to obtain the optimal functional unit assignment and voltage selection for the pipelined MPSoC systems, such that the system cost is minimized while timing constraints can be met with a given guaranteed probability. For each required probability, our proposed algorithm can efficiently obtain the optimal solution. Experiments show that other existing algorithms cannot find feasible solutions in most cases, but ours can. Even for those solutions that other algorithms can obtain, ours can reach 30% reductions in total cost compared with others.

With the development of embedded devices, elevator group systems that manage elevators can be designed in an intelligent way. In the design of elevator group systems, one of the most important problems is to determine the “range assignment” for each elevator, which indicates the floors that an elevator will serve. In reality, the traffic loads of a building are different in terms of time periods, called fluctuant traffic loads, which makes the above problem much more challenging. The objective of this paper is to determine the optimal range assignment that can maximize the number of passengers served in a certain amount of time. The elevator group system can adapt to varying traffic loads and achieve fault tolerance by conducting range reassignment. In this paper, we build a Mixed Integer Linear Programming (MILP) to find the optimal range assignment. However, MILP suffers from large computational complexities and it is impractical since the elevator group system needs to response to fluctuant traffic loads in real-time. Therefore, we devise efficient algorithms to obtain near optimal solutions. Experimental results show that we can achieve 48% and 25% improvements on average in the completion time and the average waiting time, respectively.

In high-level synthesis for real-time systems, it typically employs heterogeneous functional-unit types to achieve high-performance and low-cost designs. In the design phase, it is critical to determine which functional-unit type to be mapped for each operation in a given application such that the total cost is minimized while the deadline can be met. For a path or tree structured application, existing approaches can obtain the minimum-cost assignment, called “optimal assignment”, under which the resultant system satisfies a given timing constraint. However, it is still an open question whether there exist efficient algorithms to obtain the optimal assignment for the directed acyclic graph (DAG), or more generally, the data-flow graph with cycles (cyclic DFG). For DAGs, by analyzing the property of the problem, this paper designs an efficient algorithm to obtain the optimal assignments. For cyclic DFGs, we approach this problem with the combination of retiming technique to thoroughly explore the design space. We formulate a Mixed Integer Linear Programming (MILP) model to give the optimal solution. But because of the high degree of its time complexity, we devise a practical algorithm to obtain near-optimal solutions within a minute. Experimental results show the effectiveness of our algorithms. Specifically, compared with existing techniques, we can achieve 25.70 and 30.23 percent reductions in total cost on DAGs and cyclic DFGs, respectively.

The emerging Phase Change Memory (PCM) is considered as a promising candidate to replace DRAM as the next generation main memory since it has better scalability and lower leakage power. However, the high write power consumption has become a main challenge in adopting PCM as main memory. In addition to the fact that writing to PCM cells requires high write current and voltage, current loss in the charge pumps (CPs) also contributes a large percentage of the high power consumption. The pumping efficiency of a PCM chip is a concave function of the write current. Based on the characteristics of the concave function, the overall pumping efficiency can be improved if the write current is uniform. In this paper, we propose the peak-to-average (PTA) write scheme, which smooths the write current fluctuation by regrouping write units. An off-line optimal Integer Programming (IP) formulation and an efficient online algorithm are proposed to achieve this goal. Experimental results show that PTA can improve the charge pump efficiency to ∼40% with little overhead. Meanwhile, PTA can achieve 17.0% energy reduction on average.

Spin-transfer torque random access memory (STT-RAM) is considered as a promising candidate to replace SRAM as the next generation cache memory since it has better scalability and lower leakage power. Recently, 2-bit multi-level cell (MLC) STT-RAM has been proposed to further increase data density. However, a key drawback for MLC STT-RAM is that the magnetization directions of its hard and soft domains cannot be flipped to two opposite directions simultaneously, which leads to the two-step problem in state transitions. Two-step state transitions would significantly impact the lifetime of MLC STT-RAM due to the wasted flips in the soft domains. To solve the problem, this paper proposes a novel two-step state transition minimization (TSTM) scheme, to improve the lifetime of MLC STT-RAM when it is employed in cache design. The basic idea is by sacrificing certain cells as auxiliary flags, the two-step state transitions in STT-RAM can be well eliminated. Experimental results show that the proposed scheme can improve the lifetime of MLC STT-RAM to 318.5%.

Non-Volatile Memory (NVM) is becoming an attractive candidate to be the swap area in embedded systems for its near-DRAM speed, low energy consumption, high density, and byte-addressability. Swapping data from DRAM out to NVM, however, can cause large performance/energy penalty and deplete the lifetime of NVM. Traditional swap mechanisms may need to be re-studied. Even through there are several swap mechanisms proposed for the hybrid DRAM-NVM systems, most of them have limited performance without considering the data access features of applications.

Ceph has been widely used as a distributed object store and file system due to its high availability, reliability and scalability. Strategies of data placements in Ceph composed of heterogeneous clusters can greatly affect the system performance and load balancing. For a given application, it is critical to find the optimal data placement in Ceph, such that the completion time of the application can be minimized under the load-balancing constraint. This paper presents a novel Ceph-based framework that integrally considers the load balancing and the heterogeneities, including the computational capacity and the network bandwidth. The presented framework is suitable for the applications based on the principle of moving computation rather than data across clusters, such as MapReduce. According to the Ceph-based framework and the properties of MapReduce, we formulate the Mixed Integer Linear Programming (MILP) to obtain the optimal data placement. However, because of the large computational complexity of MILP, we devise an efficient algorithm to obtain the near-optimal solutions. The experimental results show that the proposed algorithm can achieve up to 25.6% improvement on system performance, compared with the original strategy implemented in Ceph.

Real-time and temporal information services are intrinsic characteristics in vehicular networks, where the timeliness of data dissemination and the maintenance of data quality interplay with each other and influence overall system performance. In this work, we present the system architecture where multiple road side units (RSUs) are cooperated to provide information services, and the vehicles can upload up-to-date information to RSUs via vehicle-to-infrastructure (V2I) communication. On this basis, we formulate the distributed temporal data management (DTDM) problem as a two-objective problem, which aims to enhance overall system performance on both the service quality and the service ratio simultaneously. Further, we propose a multiobjective evolutionary algorithm called MO-DTDM to obtain a set of pareto solutions and analyze how to fulfill given requirements on system performance with obtained pareto solutions. Finally, we build the simulation model and give a comprehensive performance evaluation, which demonstrates the superiority of the proposed optimization method.

The growing demand for high-performance data processing stimulates the development of in-memory file systems, which exploit the advanced features of emerging non-volatile memory techniques for achieving high-speed file accesses. Existing in-memory file systems, however, are all designed for the systems with uniformed memory accesses. Their performance is poor on Non-Uniform Memory Access (NUMA) machines as they do not consider the asymmetric memory access speed and the architecture of multiple nodes. In this paper, we propose a new design of NUMA-aware in-memory file systems. We propose a distributed file system layout for leveraging the loads of in-memory file accesses on different nodes, a thread-file binding algorithm and a buffer assignment technique for increasing local memory accesses during run-time. Based on the proposed techniques, we implement a functional NUMA-aware in-memory file system, HydraFS, in Linux kernel. Extensive experiments are conducted with the standard benchmark. The experimental results show that HydraFS significantly outperforms typical existing in-memory file systems, including EXT4-DAX, PMFS, and SIMFS.

The emerging technologies of persistent memory, such as PCM, MRAM, provide opportunities for preserving files in memory. Traditional file system structures may need to be re-studied. Even though there are several file systems proposed for memory, most of them have limited performance without fully utilizing the hardware at the processor side. This paper presents a framework based on a new concept, “File Virtual Address Space”. A file system, Sustainable In-Memory File System (SIMFS), is designed and implemented, which fully utilizes the memory mapping hardware at the file access path. First, SIMFS embeds the address space of an open file into the process' address space. Then, file accesses are handled by the memory mapping hardware. Several optimization approaches are also presented for the proposed SIMFS. Extensive experiments are conducted. The experimental results show that the throughput of SIMFS achieves significant performance improvement over the state-of-the-art in-memory file systems.

Applications that run in the embedded systems normally should be finished within a timing constraint in energy-efficient fashion. Due to these two requirements, the embedded systems often employ software-controlled scratch pad memory (SPM) instead of hardware-controlled cache as their on-chip memory. The data accesses in SPMs are controlled purely by the software, which provides better time-predictability and precise time-control. In this paper, we propose a time, energy, and area efficient domain wall memory (DWM)-based SPM for embedded systems. To efficiently manage this type of novel SPM, an integer nonlinear programming formulation and the instructions group schedule algorithm are proposed to generate memory access instruction scheduling and data placement. In addition, the longest move reduce algorithm is also proposed to configure different types of DWM memory cells to achieve minimal area size. Experimental results show that the proposed techniques can generate a configuration of DWM-based SPM with minimal area size while satisfying time constraint.

Recent advances in autonomous vehicles and vehicular communications are envisioned to enable novel approaches to managing and controlling traffic intersections. In particular, with intersection controller units (ICUs), passing vehicles can be instructed to cross the intersection safely without traffic signals. Previous efforts on autonomous intersection control mainly focused on guaranteeing the safe passage of vehicles and improving intersection throughput, without considering the quality of the travel experience from the passengers' perspective. In this paper, we aim to design an enhanced autonomous intersection control mechanism, which not only ensures vehicle safety and enhances traffic efficiency but also cares about the travel experience of passengers. In particular, we design the metric of smoothness to quantitatively capture the quality of experience. In addition, we consider the travel time of individual vehicles when passing the intersection in scheduling to avoid a long delay of some vehicles, which not only helps with improving intersection throughput but also enhances the system's fairness. With the above considerations, we formulate the intersection control model and transform it into a convex optimization problem. On this basis, we propose a new algorithm to achieve an optimal solution with low overhead. Finally, we build the simulation model and implement the algorithm for performance evaluation. Comprehensive simulation results demonstrate the superiority of the proposed algorithm.

A domain-wall memory (DWM) is becoming an attractive candidate to replace the traditional memories for its high density, low-power leakage, and low access latency. Accessing data on DWM is accomplished by shift operations that move data located on nanowires to read/write ports. Due to this kind of construction, data accesses on DWM exhibit varying access latencies. Therefore, data placement (DP) strategy has a significant impact on the performance of data accesses on DWM. In this paper, we prove the nondeterministic polynomial time (NP)-completeness of the DP problem on DWM. For the DWMs organized in single DWM block cluster (DBC), we present integer linear programming formulations to solve the problem optimally. We also propose an efficient single DBC placement (S-DBC-P) algorithm to exploit the benefits of multiple read/write ports and data locality. Compared with the sequential DP strategy, S-DBC-P reduces 76.9% shift operations on average for eight-port DWMs. Furthermore, for DP problem on the DWMs organized in multiple DBCs, we develop an efficient multiple DBC placement (M-DBC-P) algorithm to utilize the parallelism of DBCs. The experimental results show that the M-DBC-P achieves 90% performance improvement over the sequential DP strategy.

Domain Wall Memory (DWM) using nanowire with data access port, exhibits extraordinary high density, low power leakage, and low access latency. These properties enable DWM to become an attractive candidate for replacing traditional memories. However, data accesses on DWM may require multiple shift operations before the port points to requested data, resulting in varying access latencies. Data placement, therefore, has a significant impact on the performance of data accesses on DWM. This paper studies compiler-based optimization techniques for data placement on DWM. To the authors' best knowledge, this is the first work addressing data placement problem on DWM. We present an efficient heuristic, called Grouping-Based Data Placement (GBDP), for the data placement problem of a given data access sequence on DWM. The experimental results show that GBDP has a significant performance improvement; for example, GBDP reduces 82% shift operations on an 8-port DWM compared with non-optimized approach.

Domain Wall Memory (DWM), a recently developed spin-based non-volatile memory technology, inherently offers unprecedented benefits in density by storing multiple bits in the domains of a ferromagnetic nanowire, which logically resembles a bit-serial tape. However, this structure also leads to a unique challenge that the bits must be sequentially accessed by performing \shift" operations, resulting in variable and potential higher access latencies. In this paper, we propose a hardware and software co-optimize approach to improve area efficiency and performance for DWM in application-specific embedded systems. For an application-specific embedded system, this technique can obtain a DWM which consists of both micro-cell DWM and macro-cell DWM with minimal area size. Meanwhile, instruction schedule and data allocation with minimal memory access overhead are generated. Experimental results show that the proposed method can minimize the DWM area size while satisfying a system performance constraint.

Multi-core processors have been adopted in modern embedded systems to meet the ever increasing performance requirements. Scratchpad memory (SPM), a software-controlled on-chip memory, has been used in embedded systems as an alternative to hardware-controlled cache due to its advantage in die area, power consumption, and timing predictability. SPMs in multi-core systems can be accessed by both local core and remote cores. In order to alleviate data contention on a SPM unit, multi-port SPMs are employed in multi-core systems. In such systems, proper task scheduling and data assignment can significantly improve the overall performance by exploring the parallelism of computation tasks and concurrent data accesses on SPMs. Since scheduling for multi-core systems is NP-Complete in general. In this paper, we propose an ILP formulation to optimally determine the task scheduling and data assignment on multi-core systems with multi-port SPMs. Since ILP takes exponential time to finish, we also propose a heuristic method, including the task assignment with remote access reduced (TARAR) algorithm and the minimum memory access cost (MMAC) algorithm, to obtain near optimal solutions within polynomial time. According to the experimental results, the ILP formulation can improve the system performance by 23.02 percent over the HAFF algorithm on average, while the heuristic algorithm can improve the system performance by 16.48 percent over HAFF on average.

Phase change memory (PCM) is a promising DRAM replacement in embedded systems due to its attractive characteristics, such as low-cost, shock-resistivity, nonvolatility, high density, and low leakage power. However, relatively low endurance has limited its practical applications. In this paper, in addition to existing hardware level optimizations, we propose software enabled wear-leveling techniques to further extend PCMs lifetime when it is adopted in embedded systems. Most existing software optimization techniques focus on reducing the total number of writes to PCM, but none of them consider wear leveling, in which the writes are distributed more evenly over the PCM. An integer linear programming formulation and a polynomial-time algorithm, the software wear-leveling algorithm, are proposed in this paper to achieve wear leveling without hardware overhead. According to the experimental results, the proposed techniques can reduce the number of writes on the most-written addresses by more than 80% when compared with a greedy algorithm, and by more than 60% when compared with the existing optimal data allocation algorithm with under 6% memory access overhead.

Converge cast is a critical communication paradigm for data collection in wireless sensor networks, where both energy and bandwidth are scarce resources. Previous converge cast algorithms only focused on minimizing the energy cost without considering the constraint of wireless bandwidth. This article shows that constructing a congestion-free converge cast tree cannot ignore the bandwidth constraint. Considering the adjustable transmission power of sensor nodes, it will affect not only the topology of networks but also the bandwidth of wireless links. In this paper, we formulate the Minimum Total Transmission Power (MTTP) problem, which aims to address the issue of constructing a congestion-free converge cast tree in WSNs with adjustable transmission power of sensor nodes. We transform MTTP to an Integer Linear Programming (ILP) model, by which the optimal solution to MTTP is derived. To strike a balance between scheduling overhead and system performance, we propose a heuristic algorithm called Nearest-to-Sink, which searches viable paths in a greedy way and achieves near optimal performance. We build the simulation model and give a comprehensive performance evaluation, which demonstrates the feasibility and the effectiveness of the proposed algorithm.

As the advance of memory technologies, multiple types of memory such as different kinds of non-volatile memory (NVM), SRAM, DRAM, etc. provide a flexible configuration considering performance, energy and cost. For improving the performance of systems with multiple types of memory, data allocation is one of the most important tasks. The previous studies on data allocation problem assume the worst (fixed) case of data-access frequencies. However, the data allocation produced by employing worst case usually leads to an inferior performance for most of time. In this paper, we model this problem by probabilities and design efficient algorithms that can give optimal-cost data allocation with a guaranteed probability. The proposed DAGP algorithm produces a set of feasible data allocation solutions which generates the minimum access time or cost guaranteed by a given probability. The experiments show that our technique can significantly reduce the access time or cost compared with the technique considering worst case scenario. For example, comparing with the optimal result generated by employing the worst cases, our technique can reduce memory access time by 10.35% on average when guaranteed probability is set to be 0.8. Moreover, for 80 percents of cases, memory access time is reduced by 23.98% on average.

Multiprocessor System-on-Chip employing self-timed technique becomes increasingly attractive due to its ability for exploiting high parallelism of applications. There have been many research efforts on studying self-timed techniques on hardware layer. However, these research results are unable to be applied to system synthesis; in particular, how to correctly and optimally map an application represented by a Data Flow Graph to a self-timed ring architecture remains unknown. Self-timed ring (STR) is a popular and easy to implemented architecture. This paper establishes a series of theorems about the setting of initial configuration to achieve correct mappings and the formulas of calculating corresponding throughputs of STR. Based on the understanding, we can obtain a correct initial configuration of STR. And an algorithm presented in the paper can also find the best initial configuration that achieves the maximum throughput of STR. Examples show maximum throughput algorithm achieves 51.11% improvement of throughput compared with non-optimized ones.

In recent years, an emerging low-power system “wireless sensor networks (WSNs)” attracts significant research interests. The energy of the distributed sensors is an essential constraint in such a complex distributed embedded system. Routing techniques in WSNs always follow a high-performance and energy-efficient way. However, conventional routing schemes of WSNs generally do not take the timing and reliability requirements into account when making routing decisions to prolong the lifetime of WSNs. Moreover, due to environmental factors such as temperature, humidity and signal interference, the bandwidths of links in a WSN various from time to time like random variables, which demands special considerations when timing and reliability requirements are presented for routing. In this paper, we introduce a graph model called Multi-level Uncertain Graph (MUG) to deal with the situation. Based on the MUG model, we define the new problem as the Energy-Balanced Transmission (EBT) Problem, and propose a EBT-Solver to maximize the lifetime of the WSN subject to timing and reliability constraints. Experimental results show that EBT-Solver solves EBT problem to the best advantage of energy balance and network's lifetime.

Phase Change Memory (PCM) has been considered as a leading candidate to replace the traditional DRAM in embedded systems due to its promising characteristics such as low leakage power, low cost, non-volatility, and high scalability. One of the constraints that undermine the credential of PCM as main memory is its limited write endurance. In this paper, we develop wear-leveling techniques purely on the Operating System (OS) level to extend lifetime of PCM. Without extra hardware support, OS management is more flexible to be integrated into existing embedded systems. To achieve wear-leveling, the Periodical Page Swapping (PPS), Rearrangement Inequality Based Page Allocation (RIPA), and Write Intensity Based Process Scheduling (WIPS) algorithms are proposed in this paper on OS level. The experimental results show that the proposed techniques can significantly extend the lifetime of PCM main memory.

It is common that embedded systems are powered by limited and unstable power supply. In order to improve the reliability of embedded systems against unstable power supply, non-volatile memory (e.g. FRAM) based registers are proposed for embedded processors. FRAM-based registers have many advantages over traditional CMOS-based volatile registers such as non-volatility and power-economy. However, similar to other non-volatile memories (NVM), write operations to FRAM consume more time and power compared with read operations and limit the lifetime of the registers. Existing compiler optimization techniques never take the writes to registers into consideration. Therefore, code generated by a traditional compiler has an adverse effect on processors with non-volatile registers. This paper aims at improving the lifetime and efficiency of non-volatile registers based embedded processors by generating NV register friendly code. To achieve the goal, in this paper, we investigate the usage of memory access instructions and propose the NV Register Aware Instruction Selection (NAIS) algorithm to reduce the write operations on non-volatile registers. According to the experimental results, the proposed algorithm can reduce the writes on NV registers by 66.89% on average when compared with GCC [1]. Thus the lifetime of NV registers is extended to 2 times as long as before on average. The time cost is reduced by 56.68% and the energy consumption is reduced by 59.76% on average.

To satisfy the ever increasing performance requirement of applications, Multiprocessor System-on-Chip (MPSoC) plays an irreplaceable role in embedded system these days. It is significant to effectively optimize communication for achieving maximum parallelism on MPSoC, especially on Network-on-Chip (NoC) based architectures. The problem of how to make an arbitration of communication congestion is remained unsolved. In this paper, we propose a reasonable Unified Priority-Based Scheduling (UPS) algorithm for task and communication co-scheduling with communication contention, which is based on a novel Task Communication Graph (TCG) model of an application. The proposed method is more accurate and effective to describe the overall process of applications. The experimental results show that the performance is improved by 31.1% on average of scheduling generated by our algorithm. It verifies that the proposed method in this paper can improve the performance of contention-aware task and communication scheduling on NoC-based MPSoC architecture.

In power and size sensitive embedded systems, non-volatile memories (NVMs) are replacing DRAM as the main memory since they have higher density, lower static power consumption, and lower costs. Unfortunately, these technologies are limited by their endurance and long write latencies. To minimize the main memory access time and extend the lifetime of the NVM, we optimally schedule tasks by an ILP formulation. We also present a heuristic, Concatenation Scheduling, to solve large problems in a reasonable amount of time. Our experimental results show that when compared with list scheduling, concatenation scheduling can reduce the total memory access time by an average of 9.99% and increase the lifetime of the NVM by 26.66%. When compared with list scheduling, ILP can reduce the total memory access time by an average of 12.39% and increase the lifetime of the NVM by 38.74%.

Phase change memory (PCM) has been proposed to replace NOR flash and DRAM in embedded systems because of its attractive features. However, the endurance of PCM greatly limits its adoption in embedded systems. As most embedded systems are application-oriented, we can tackle the endurance problem of PCM by exploring application-specific features such as fixed access patterns and update frequencies. In this paper, we propose an application-specific wear leveling technique, called Curling-PCM, to evenly distribute write activities across the whole PCM chip to improve the endurance of PCM in embedded systems. The basic idea is to exploit application-specific features in embedded systems and periodically move the hot region across the whole PCM chip. To reduce the overhead of moving the hot region and improve the performance of PCM-based embedded systems, a fine-grained partial wear leveling policy is proposed for Curling-PCM, by which only part of the hot region is moved during each request handling period. Experimental results show that Curling-PCM can effectively evenly distribute write traffic for a prime application of PCM in embedded systems. We expect this paper can serve as a first step toward the full exploration of application-specific features in PCM-based embedded systems.

The recent emergence of various Non-Volatile Memories (NVMs), with many attractive characteristics such as low leakage power and high-density, provides us with a new way of addressing the memory power consumption problem. In this article, we target embedded CMPs, and propose a novel Hybrid Scratch Pad Memory (HSPM) architecture which consists of SRAM and NVM to take advantage of the ultra-low leakage power, high density of NVM, and fast access of SRAM. A novel data allocation algorithm as well as an algorithm to determine the NVM/SRAM ratio for the novel HSPM architecture are proposed. The experimental results show that the data allocation algorithm can reduce the memory access time by 33.51% and the dynamic energy consumption by 16.81% on average for the HSPM architecture when compared with a greedy algorithm. The NVM/SRAM size determination algorithm can further reduce the memory access time by 14.7% and energy consumption by 20.1% on average.

High-performance computing systems typically employ heterogeneous multicore design to improve both execution performance and efficiency. Task assignment is critical in exploiting the diversity of computation capability, energy consumption, as well as communication cost on heterogeneous multicore processors. In this paper, we explore the opportunity of task assignment on heterogeneous multicore processors to minimize execution and communication costs considering time constraint. The general heterogeneous task assignment problem is NP-Complete. However, we find that optimal task assignment can be achieved for widely used, tree-shaped task graphs using dynamic programming. We first propose a dynamic programming algorithm, the Optimal Tree Assign (OTA) algorithm, to generate optimal assignments for trees. Then, we develop the Integer Linear Programming model of the general task assignment problem for Directed Acyclic Graphs. A polynomial-time heuristic, the Extended Tree Assignment algorithm, is also proposed to produce near-optimal solutions for the general heterogeneous task assignment problem efficiently. The experimental results show that the proposed algorithms outperform both homogeneous task assignment method and greedy strategy for all the benchmarks. The OTA algorithm reduces the total system time by 42.5 percent and 23.5 percent on average compared with the homogeneous task assignment method and greedy algorithm, respectively.

Phase change memory (PCM) has been used as NOR flash replacement in embedded systems with its attractive features. However, the endurance of PCM keeps drifting down and greatly limits its adoption in embedded systems. As most embedded systems are application-oriented, we can better utilize PCM by exploring application-specific features such as fixed access patterns and update frequencies to prolong the lifetime of PCM. In this paper, we propose an application-specific wear leveling technique, called Curling-PCM, to evenly distribute write activities across the PCM chip in order to improve the endurance of PCM. The basic idea is to exploit application-specific features in embedded systems and periodically move the hot region across the whole PCM chip. To further reduce the overhead of moving the hot region and improve the performance of PCM-based embedded systems, a fine-grained partial wear leveling policy is proposed in Curling-PCM, by which only part of the hot region is moved during each request handling period. The experimental results show that Curling-PCM can effectively evenly distribute write traffic in PCM chips compared with previous work. We expect this work can serve as a first step towards the full exploration of application-specific features in PCM-based embedded systems.

Phase Change Memory (PCM) is a promising DRAM replacement in embedded systems due to its attractive characteristics. However, relatively low endurance has limited its practical applications. In this paper, in additional to existing hardware level optimizations, we propose software enabled wear-leveling techniques to further extend PCM's lifetime when it is adopted in embedded systems. A polynomial-time algorithm, the Software Wear-Leveling (SWL) algorithm, is proposed in this paper to achieve wear-leveling without hardware overhead. According to the experimental results, the proposed technique can reduce the number of writes on the most-written bits by more than 80% when compared with a greedy algorithm, and by around 60% when compared with the existing Optimal Data Allocation (ODA) algorithm with under 6% memory access overhead.

Virtually Shared Scratch-Pad Memory (VS-SPM) with multiple memory banks can be used as on-chip memory on multiprocessor systems-on-chips (MPSoCs) to close the speed gap between fast processors and slow memories. By exploring the parallelism of computation tasks on processors and concurrent data accesses on each SPM, the results of task assignment and data allocation can significantly affect the overall performance of a schedule. In this paper, we propose ILP formulations for solving the problem of task assignment and scheduling on MPSoCs with multi-bank VS-SPM.We also propose a polynomial-time algorithm, the Potential Remote Access Prediction (PRAP) algorithm, to generate near-optimal results efficiently. The experimental results demonstrate the effectiveness of our technique.

Phase change memory (PCM) has emerged as a promising candidate to replace DRAM in embedded systems. However, it can only sustain a limited number of write operations. To solve this issue, this paper proposes a novel and effective wear-leveling technique in software level to prolong the lifetime of PCM-based embedded systems. A polynomial-time algorithm, Multi-Space Wear Leveling Algorithm (MWL), is proposed to achieve effective wear-leveling. The experimental results show our technique can greatly extend the lifetime of PCM-based embedded systems compared with the previous work. Compared with the method without adopting wear-leveling, it introduces no more than 0.7% extra writes and 0.6% running overhead.

Effective task assignment, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. This paper addresses the task assignment problem with guaranteed reliability and timing constraint for heterogeneous multiprocessor system. Inherently, heterogeneous systems are more complex than homogeneous systems. The added complexity could increase the potential for system failures. In this paper, we describe a method to determine an assignment which satisfies the timing constraint and the reliability requirement. We develop an Integer Linear Programming (ILP) formulation to find the optimal solutions. For the general problem, the task assignment problem is NP-Complete. Therefore, we propose a polynomial-time heuristic algorithm, DAG Heu algorithm, to solve the general problem. Experimental results on benchmark task graphs of several well-known parallel applications show that the proposed algorithm and the ILP formulation significantly outperform existing algorithms.

Scratch pad memories (SPM) are attractive alternatives for caches on multicore systems since caches are relatively expensive in terms of area and energy consumption. The key to effectively utilizing SPMs on multicore systems is the data placement algorithm. In this paper, two polynomial time algorithms, regional data placement for multicore (RDPM) and regional data placement for multicore with duplication (RDPM-DUP), have been proposed to generate near-optimal data placement with minimum total cost. There is only one copy for each data in RDPM, while RDPM-DUP allows data duplication. Experimental results show that the proposed RDPM algorithm alone can reduce the time cost of memory accesses by 32.68% on average compared with existing algorithms. With data duplication, the RDPM-DUP algorithm further reduces the time cost by 40.87%. In terms of energy consumption, the proposed RDPM algorithm with exclusive copy can reduce the total cost by 33.47% on average. When RDPM-DUP is applied, the improvement increases up to 38.15% on average.

Recent advances in circuit and semiconductor technologies have pushed Non-Volatile Memory (NVM) technologies into a new era. These technologies exhibit appealing properties such as low power consumption, non-volatility, shock-resistivity, and high density. However, there are challenges to which we need answers in the road of applying non-volatile memories as main memory in embedded computer systems. First, when compared with DRAM, NVMs have a limited number of write/erase cycles. Second, write activities on NVM are more expensive than DRAM memory in terms of energy consumption and access latency. Both challenges will benefit from the reduction of the write activities on the NVMs. In this paper, we target embedded Chip Multiprocessors (CMPs) with Scratch Pad Memory (SPM) and non-volatile main memory. We introduce scheduling, data migration, and recomputation techniques to reduce the number of write activities on NVMs. Experimental results show that the proposed methods can reduce the number of writes by 58.46% on average, which means that the NVM can last 2.8 times as long as before. For Phase Change Memory (PCM), the lifetime is extended from 2.5 years to about 7 years on average and 15 years at the most. Also, the finish time of the tested programs is reduced by an average of 38.07%, and the energy consumption is reduced by an average of 51.23%.

Embedded systems normally have a tight energy budget. Since the on-chip cache typically consumes 25%-50% of the processor's area and energy consumption, scratch pad memory (SPM), which is a software-controlled on-chip memory, has been widely adopted in many embedded systems due to its smaller area and lower power consumption. However, as the speed of the CMOS transistors increases along with density, leakage power consumption is becoming a critical issue for memory components with a large number of transistors. In this paper, we propose a novel hybrid SPM which consists of static random-access memory (SRAM) and nonvolatile memory (NVM) to take advantage of the ultralow leakage power and high density of latter. A novel dynamic data management algorithm is also proposed to make use of the full potential of NVM. According to the experimental results, with the help of the proposed algorithm, the novel hybrid SPM architecture can reduce the memory access time by 18.17%, the dynamic energy by 24.29%, and the leakage power by 37.34% compared with a baseline pure SRAM SPM with the same area.

In embedded systems power consumption and area tightly constrain the cache capacity and management logic. Many good cache replacement policies have been proposed in the past, but none approach the performance of the least recently used (LRU) algorithm without incurring high overheads. In fact, many embedded designers consider even pseudo-LRU too complex for their embedded systems processors. In this paper, we propose a new level 1 (L1) data cache replacement algorithm, Protected Round-Robin (PRR) that is simple enough to be incorporated into embedded processors while providing miss rates that are very similar to the miss rates of LRU. Our experiments showed that on average the miss rates of PRR are only 0.22% higher than the miss rates of LRU on a 32KB, 4-way L1 data cache with 32 byte long cache lines. PRR has miss rates that are on average 4.72% and 4.66% lower than random and round-robin replacement algorithms, respectively.

Non-Volatile Memories (NVMs) have many advantages over traditional DRAM. It is desirable to apply NVM as main memory in embedded Chip Multi-Processor (CMP) systems. However, NVMs have drawbacks that need to be overcome. That is, a write to the NVMs is expensive. Loops are the most critical and time-consuming part in digital signal processing (DSP) applications. However, loops are difficult to parallelize on multi-processor systems due to the inter-iteration dependencies. This paper targets on embedded CMP systems and proposes techniques to improve loop parallelism while considering reducing the write activities to the NVMs when they are used as main memory. The experimental results show that the proposed algorithm can reduce the number of write activities on NVM by 21.1% on average. In other words, the average lifetime of NVM can be extended to at least 2 times longer than before and the total schedule length is reduced by 19.6% on average.

Scratch Pad Memory (SPM), a software-controlled on-chip memory, is popular in embedded systems due to its many benefits. To efficiently manage SPM, many different data allocation algorithms are proposed. However, most of them cannot achieve optimal results. In this paper, we proposed a dynamic programming approach, Iterational Optimal Data Allocation (IODA) to allocate data for embedded systems with multiple types of memory units. According to the experimental results, the IODA algorithm lowered the energy consumption by 20.14% and 5.11% compared to a random memory allocation and a greedy algorithm, respectively. It also reduced the memory access time by 18.44% and 5.83% compared to a random memory allocation and a greedy algorithm, respectively.

Scratch Pad Memory (SPM), a software-controlled on-chip memory, has been widely adopted in many embedded systems due to its small area and low power consumption. As technology scaling reaches the sub-micron level, leakage energy consumption is surpassing dynamic energy consumption and becoming a critical issue. In this paper, we propose a novel hybrid SPM which consists of non-volatile memory (NVM) and SRAM to take advantage of the ultra-low leakage power consumption and high density of NVM as well as the efficient writes of SRAM. A novel dynamic data allocation algorithm is proposed to make use of the full potential of both NVM and SRAM. According to the experimental results, with the help of the proposed algorithm, the novel hybrid SPM architecture can reduce memory access time by 18.17%, dynamic energy by 24.29%, and leakage power by 37.34% on average compared with a pure SRAM based SPM with the same size area.

Multi-core systems have been a popular design for high-performance embedded systems. Scratch Pad Memory (SPM), a software-controlled on-chip memory, has been widely adopted in many embedded systems due to its small area and low energy consumption. Existing data allocation algorithms either cannot achieve optimal results or take exponential time to complete. In this paper, we propose one polynomial-time algorithms to solve the data allocation problem on multi-core system with exclusive data copy. According to the experimental results, the proposed optimal data allocation method alone reduces time cost of memory accesses by 16.45% on average compared with greedy algorithm. The proposed data allocation algorithm also can reduce the energy cost significantly.

Scratch-Pad Memory (SPM) has been widely adopted in many embedded systems as well as digital signal processor systems. This paper proposes a polynomial time optimal data placement algorithm to minimize the memory access cost of one program region for memory architectures with multiple types of memory units including SPM in order to achieve high performance with low cost. The experimental results show our algorithms can reduce time cost of memory access by 18.19% and the energy cost by 16.97% compared with random data placement, which is better than the existing greedy algorithms.

Nonvolatile memories such as Flash memory, phase change memory (PCM), and magnetic random access memory (MRAM) have many desirable characteristics for embedded systems to employ them as main memory. However, there are two common challenges we need to answer before we can apply nonvolatile memory as main memory practically. First, nonvolatile memory has limited write/erase cycles compared to DRAM. Second, a write operation is slower than a read operation on nonvolatile memory. These two challenges can be answered by reducing the number of write activities on nonvolatile main memory. In this paper, we proposed two optimization techniques, write-aware scheduling and recomputation, to minimize write activities on nonvolatile memory. With the proposed techniques, we can both speed up the completion time of programs and extend nonvolatile memory's lifetime. The experimental results show that the proposed techniques can reduce the number of write activities on nonvolatile memory by 55.71% on average. Thus, the lifetime of nonvolatile memory is extended to 2.5 times as long as before on average. The completion time of programs can be reduced by 56.67% on systems with NOR Flash memory and by 47.63% on systems with NAND Flash memory on average.

In power and size sensitive embedded systems, flash memory and phase change memory are replacing DRAM as the main memory. Unfortunately, these technologies are limited by their endurance and long write latencies. To minimize the main memory access time, we optimally schedule tasks by an ILP formulation that can be generally applied to other main memory technologies, including DRAM. We also present a heuristic, Wander Scheduling, to solve larger instances in a reasonable amount of time. Our experimental results show that when compared with list scheduling, Wander Scheduling can reduce memory access times by an average of 40.73% and increase the lifetime of flash and phase change memory by 82.56%.

Low energy consumption is an important problem in real-time embedded systems and loop is the most energy consuming part in most cases. Due to the uncertainties in execution time of some tasks, this paper models each varied execution time as a probabilistic random variable. We use rotation scheduling and DVS (Dynamic Voltage Scaling) to minimize the expected total energy consumption while satisfying the timing constraint with a guaranteed confidence probability. Our approach can handle loops efficiently. In addition, it is suitable to both soft and hard real-time systems. And even for hard real-time, we have good results.

With more embedded systems networked, it becomes an important problem to effectively defend embedded systems against buffer overflow attacks. Due to the increasing complexity and strict requirements, off-the-shelf software components are widely used in embedded systems, especially for military and other critical applications. Therefore, in addition to effective protection, we also need to provide an approach for system integrators to efficiently check whether software components have been protected. In this paper, we propose the HSDefender (Hardware/Software Defender) technique to perform protection and checking together. Our basic idea is to design secure call instructions so systems can be secured and checking can be easily performed. In the paper, we classify buffer overflow attacks into two categories and provide two corresponding defending strategies. We analyze the HSDefender technique with respect to hardware cost, security, and performance. We experiment with our HSDefender technique on the simplescalar/ARM simulator with benchmarks from MiBench, an embedded benchmark suite. The results show that our HSDefender technique can defend a system against more types of buffer overflow attacks with less overhead compared with the previous work.

In embedded systems, high-performance DSP needs to be performed not only with high-data throughput but also with low-power consumption. This article develops an instruction-level loop-scheduling technique to reduce both execution time and bus-switching activities for applications with loops on VLIW architectures. We propose an algorithm, SAMLS (Switching-Activity Minimization Loop Scheduling), to minimize both schedule length and switching activities for applications with loops. In the algorithm, we obtain the best schedule from the ones that are generated from an initial schedule by repeatedly rescheduling the nodes with schedule length and switching activities minimization based on rotation scheduling and bipartite matching. The experimental results show that our algorithm can reduce both schedule length and bus-switching activities. Compared with the work of Lee et al. [2003], SAMLS shows an average 11.5% reduction in schedule length and an average 19.4% reduction in bus-switching activities.

This paper addresses high level synthesis for realtime digital signal processing (DSP) architectures using heterogeneous functional units (FUs). For such special purpose architecture synthesis, an important problem is how to assign a proper FU type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. In the paper, we propose a two-phase approach to solve this problem. In the first phase, we propose an algorithm to assign proper FU types to applications such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained in the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. The experimental results show that our approach can generate high-performance assignments and schedules with great reduction on total cost compared with the previous work.

This paper addresses high level synthesis for real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs). For such special purpose architecture synthesis, an important problem is how to assign a proper FU type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. We propose a two-phase approach to solve this problem. In the first phase, we solve the heterogeneous assignment problem, i.e., how to assign proper FU types to applications such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained in the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. We prove that the heterogeneous assignment problem is NP-complete. Efficient algorithms are proposed to find an optimal solution when the given DFG is a simple path or a tree. Three other algorithms are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost compared with the previous work.

Loop fusion is commonly used to improve the instruction-level parallelism of loops for high-performance embedded computing systems. Loop fusion, however, is not always directly applicable because the fusion prevention dependencies may exist among loops. Most of the existing techniques still have limitations in fully exploiting the advantages of loop fusion. In this paper, we present a general loop fusion technique for loops or nested loops based on the loop dependency graph model, retiming, and multi-dimensional retiming concepts. We show that any "J+K" model loop can be legally fused using our legalizing fusion technique. Polynomial-time algorithms are developed to solve the loop fusion problem for "J+K" model loops considering both timing and code size of the final code. Our technique produces the final code and calculates the resultant code size directly from the retiming values. The experimental results show that our loop fusion technique always significantly reduces the schedule length.

Previous approaches for the shortest path tree (SPT) dynamic update have mainly focused on the case of one link state change. Little work has been done on the problem of deriving a new SPT based on its old one for multiple link state decrements in a network that applies link-state routing protocols. The complexity of this problem comes from there being no accurate boundary of nodes to be updated in an updating process and that multiple decrements can be accumulated. Two dynamic algorithms (MaxR, MinD) are proposed to reduce the times for node updating. Compared with other algorithms for the SPT update of multiple edge weight decrements, our algorithms yield fewer times for node updates during the dynamic update process. Such an achievement is attained by the mechanism of part node updating in a branch on the SPT after a particular node selection from a built node list. Simulation results are given to show our improvements.

Software pipelining for nested loops remains a challenging problem for embedded system design. The existing software pipelining techniques for single loops can only explore the parallelism of the innermost loop, so the final timing performance is inferior. While multidimensional (MD) retiming can explore the outer loop parallelism, it introduces large overheads in loop index generation and code size due to transformation. We use MD retiming to model the software pipelining problem of nested loops. We show that the computation time and code size of a software-pipelined loop nest is affected by execution sequence and retiming function. The algorithm of software pipelining for nested loops technique (SPINE) is proposed to generate fully parallelized loops efficiently with the overheads as small as possible. The experimental results show that our technique outperforms both the standard software pipelining and MD retiming significantly.

Summary form only given. In high level synthesis for real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs), an important problem is how to assign a proper fit type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. We propose a two-phase approach to solve this problem. In the first phase, we solve heterogeneous assignment problem, i.e., how to assign a proper FU type to a DSP application such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained from the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. We prove heterogeneous assignment problem is NP-complete and propose several algorithms to solve it. The experiments show that algorithm DFG-assign-repeat is the best that gives a reduction of 25.7% on total cost compared with the previous work.

Buffer over-flow attacks have been causing serious security problems for decades. With more embedded systems networked, it becomes an important research problem to defend embedded systems against buffer overflow attacks. We propose the hardware/software address protection (HSAP) technique to solve this problem. We first classify buffer overflow attacks into two categories (stack smashing attacks and function pointer attacks) and then provide two corresponding defending strategies. In our technique, hardware boundary check method and function pointer XOR method are used to protect a system against stack smashing attacks and function pointer attacks, respectively. Although the focus of the HSAP technique is on embedded systems because of the availability of hardware support, we show that the HSAP technique is applied to any type of processors to defend against buffer overflow attacks. We use four classes of processors to illustrate that the applicability of our technique is independent of architectures. We experiment with our HSAP technique in ARM Evaluator-7T simulation development environments. The results show that our HSAP technique defends a system against more types of buffer overflow attacks with little overhead.

Software pipelining technique is extensively used to exploit instruction-level parallelism of loops, but also significantly expands the code size. For embedded systems with very limited on-chip memory resources, code size becomes one of the most important optimization concerns. This paper presents the theoretical foundation of code size reduction for software-pipelined loops based on retiming concept. We propose a general Code-size REDuction technique (CRED) for various kinds of processors. Our CRED algorithms integrate the code size reduction with software pipelining. The experimental results show the effectiveness of the CRED technique on both code size reduction and code size/performance trade-off space exploration.

Code size expansion of software-pipelined loops is a critical problem for DSP systems with strict code size constraint. Some ad-hoc code size reduction techniques were used to try to reduce the prologue/epilogue produced by software pipelining. We present the fundamental understanding of the relationship between code size expansion and software pipelining. Based on the retiming concept, we present a powerful Code-size REDuction (CRED) technique and its application on various kinds of processors. We also provide CRED algorithms integrated with the software pipelining process. One advantage of our algorithms is that it can explore the trade-off space between "perfect" software pipelining and constrained code size. That is, the software pipelining process can be controlled to generate a schedule concerned with code size requirement. The experiment results show the effectiveness of our algorithms in both reducing the code size for software-pipelined loops and exploring the code size/performance trade-off space.

Shortest path tree (SPT) computation is the major over-head for routers using any link-state routing protocols including the most widely used OSPF and IS-IS. Changes of link states are nowadays commonly occurred. It is not efficient and stable for network routing to use traditional static SPT algorithms to recompute the whole SPT whenever a change happens. We present new dynamic algorithms to compute and update the SPT with the minimum computational overhead. Routing stability is achieved by having the minimum changes in the topology of an existing SPT when some link states are changed. To the authors' knowledge, our algorithms outperform the best existing ones in the literature.