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.

As one of the most frequently occurring operations, I/Os significantly affect the application launching time and frame rate of mobile devices, hence influencing the user experience. However, the response speed of I/O requests is still the bottleneck in practice. This paper shows that high I/O latency is usually due to the congestion inside Flash instead of the system layer. Unfortunately, Flash is treated as a black box device and cannot be modified after delivery. In this paper, we propose a novel service to address this issue without an intra-Flash modification. Specifically, this paper proposes a lightweight I/O throttling framework in mobile systems named FlashDAM. This service throttles the I/O flow to make way for I/Os that may block the foreground application. FlashDAM is the first work that proves that proper I/O throttling positively affects the user experience, contrary to the common belief. Furthermore, this paper proposes FlashDAM$^+$, an enhanced version of FlashDAM. By coordinating I/O throttling and compression, FlashDAM's effect in the system layer is minimized. We have implemented FlashDAM on real mobile devices. Experimental results illustrate that the app launching speed and frame rate are enhanced by 72% and 45% separately compared to the state-of-the-art. When enabling the compression feature of FlashDAM, that is, FlashDAM$^+$, screen jank and application launch latency are further reduced by 9.5% and 11.4%, respectively, under heavy background I/O load.

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.

Hybrid solid state drives (SSDs) that integrate high-performance and large-capacity flash are widely used due to their cost-effectiveness. The TRIM command, which is a popular command in normal SSDs to improve performance and endurance, is also recommended in hybrid SSDs. However, employing TRIM on hybrid SSDs as on normal SSDs will induce performance loss and sub-optimal endurance due to the different characteristics of flash in hybrid SSDs. To solve the problem, this paper first explores the critical factors of issuing TRIM commands to different flash. Then, this paper proposed a differential TRIM method (dTRIM), which suggests performing early TRIM on high-performance flash and lazy TRIM on high-capacity flash. Specifically, early TRIM will minimize garbage collection costs while lazy TRIM tries to avoid conflicting user requests. Experimental results demonstrate that dTRIM can significantly improve the performance and endurance of hybrid SSDs compared with the state-of-the-arts.

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.

I/O plays an important role in the user experience. However, their quick response cannot be ensured in mobile systems, which is always blamed by users. Our study indicates that poor response is always caused by Flash-device side congestion, instead of I/O scheduling in the system layer. Unfortunately, the Flash device is treated as a black box and is not allowed to be modified after delivery. This paper explores a new approach to address the in-device problem without any invasive modification in the Flash. In this paper, we propose FlashDAM, a flexible I/O throttling framework in mobile systems. Contrary to the common belief, FlashDAM shows that proper I/O throttling, rather than straightforward boosting, has a positive effect on the user experience. We have implemented FlashDAM on off-the-shelf smartphones. Experimental results show that the application launch speed and frame rate stability can be enhanced by 72% and 45% separately, compared to the state-of-the-art.

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.

Mobile systems and applications are becoming increasingly feature-rich and powerful, which constantly suffer from memory pressure, especially for devices equipped with limited DRAM. Swapping inactive DRAM pages to the storage device is a promising solution to extend the physical memory. However, existing mobile devices usually adopt flash memory as the storage device, where swapping DRAM pages to flash memory may introduce significant performance overhead. In this paper, we first conduct an in-depth analysis of the I/O characteristics of the flash-based memory swapping, including the I/O interference and swap I/O randomness in swap subsystem. Then an I/O efficiency optimization framework for memory swapping (IOSR) is proposed to enhance the performance of flash-based memory swapping for mobile devices. IOSR consists of two methods: swap I/O scheduling (SIOS) and swap I/O pattern reshaping (SIOR). SIOS is designed to schedule the swap I/O to reduce interference with other processes I/Os. SIOR is designed to reshape the swap I/O pattern with process-oriented swap slot allocation and adaptive granularity swap read-ahead. IOSR is implemented on Google Pixel 4. Experimental results show that IOSR reduces the application switching time by 31.7% and improves the swap-in bandwidth by 35.5% on average compared to the state-of-the-art.

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.

Hybrid flash based storage constructed with high-density and low-cost flash memory are becoming increasingly popular in consumer devices during the last decade. However, to protect critical data, existing methods are designed for improving reliability of consumer devices with non-hybrid flash storage. Based on evaluations and analysis, these methods will result in significant performance and lifetime degradation in consumer devices with hybrid storage. The reason is that different kinds of memory in hybrid storage have different characteristics, such as performance and access granularity. To address the above problems, a critical data backup (CDB) method is proposed to backup designated critical data with making full use of different kinds of memory in hybrid storage. Experiment results show that compared with the state-of-the-arts, CDB achieves encouraging performance and lifetime improvement.

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.

Flash memory has been developed with bit density improvement, technology scaling, and 3-D stacking. With this trend, its reliability has been significantly degraded. Error correction code (ECC), such as low-density parity code (LDPC), which has strong error correction capability, has been deployed to solve this problem. However, one of the critical issues of LDPC is that it would introduce a long decoding latency on devices with low reliability. In this case, tail latency would happen, which will significantly impact the quality of service. In this work, a set of smart refresh schemes is proposed to optimize the tail latency. The basic idea of the work is to refresh data when the accessed data have a long decoding latency. Two smart refresh schemes are proposed for this work. The first refresh scheme is designed to refresh data with a long access latency when they are accessed several times. The second refresh scheme is designed to periodically check data with an extremely long access latency and refresh them. To further optimize the refresh overhead caused by the above refresh schemes, a dual-ECC-based refresh scheme is proposed. Besides, a mathematical model for all proposed schemes is constructed to clarify the benefit of each scheme. The experimental results show that the proposed schemes can significantly improve the tail latency with acceptable overhead. What is more, the access performance is well maintained compared with the state-of-the-art work.

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.

With the development of NAND flash technology, hybrid SSDs with high-density and low-cost flash memory have become the mainstream of the existing SSD architecture. In this architecture, two flash modes can be dynamically switched, such as single-level cell (SLC) mode and quad-level cell (QLC) mode. Based on evaluations and analysis of multiple real devices, this paper presents two interesting findings. They demonstrate that the coordination between the two flash-modes is not well-designed in existing architectures. This paper proposes HyFlex, which redesigns the strategies of data placement and flash-mode management of hybrid SSDs in a flexible approach. Specifically, two novel optimization strategies are proposed: velocity-based I/O scheduling (VIS) and garbage collection (GC)-aware capacity tuning (GCT). Experimental results show that HyFlex achieves encouraging performance and endurance improvement.

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.

Hardware-aware Neural Architecture Search (NAS), which automatically finds an architecture that works best on a given hardware design, has prevailed in response to the ever-growing demand for real-time Artificial Intelligence (AI). However, in many situations, the underlying hardware is not pre-determined. We argue that simply assuming an arbitrary yet fixed hardware design will lead to inferior solutions, and it is best to co-explore neural architecture space and hardware design space for the best pair of neural architecture and hardware design. To demonstrate this, we employ Network-on-Chip (NoC) as the infrastructure and propose a novel framework, namely NANDS, to co-explore NAS space and NoC Design Search (NDS) space with the objective to maximize accuracy and throughput. Since two metrics are tightly coupled, we develop a multi-phase manager to guide NANDS to gradually converge to solutions with the best accuracy-throughput tradeoff. On top of it, we propose techniques to detect and alleviate timing performance bottleneck, which allows better and more efficient exploration of NDS space. Experimental results on common datasets, CIFAR10, CIFAR-100 and STL-10, show that compared with state-of-the-art hardware-aware NAS, NANDS can achieve 42.99% higher throughput along with 1.58% accuracy improvement. There are cases where hardware-aware NAS cannot find any feasible solutions while NANDS can.

Solid state drives (SSDs) are now widely deployed due to the development of high-density and low-cost NAND flash memories. Previous works have identified that the read performance of SSDs is degrading along with the development. One of the most critical reasons is the access interference between reads and writes, as the latest NAND flash memories have significant latency gap between reads and writes. This paper addresses this issue with the assistance of access characteristic guided SSD partitioning. First, several server workloads are studied and it is shown that reads and writes can be separated based on their access characteristics. Second, a set of techniques is proposed to place data judiciously for requests separation. Finally, a workload based SSD partitioning scheme is proposed to improve the read performance. The experimental results show that the proposed solution can improve read performance by 36% on average compared with the state-of-the-art solutions.

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.

Three-dimensional (3D) NAND flash has been developed to boost the storage capacity by stacking memory cells vertically. One critical characteristic of 3D NAND flash is its large endurance variation. With this characteristic, the lifetime will be determined by the unit with the worst endurance. However, few works can exploit the variations with acceptable overhead for lifetime improvement. In this paper, a variation-aware lifetime improvement framework is proposed. The basic idea is motivated by an observation that there is an elegant matching between unit endurance and wearing variations when wear leveling and implicit compression are applied together. To achieve the matching goal, the framework is designed from three-type-unit levels, including cell, line, and block, respectively. Series of evaluations are conducted, and the evaluation results show that the lifetime improvement is encouraging, better than that of the combination with the state-of-the-art schemes.

Flash memory has been developed with bit density improvement, technology scaling, and 3D stacking. With this trend, its reliability has been degraded significantly. Error correction code, low density parity code (LDPC), which has strong error correction capability, has been employed to solve this issue. However, one of the critical issues of LDPC is that it would introduce a long decoding latency on devices with low reliability. In this case, tail latency would happen, which will significantly impact the quality of service (QoS). In this work, a set of smart refresh schemes is proposed to optimize the tail latency. The basic idea of the work is to refresh data when the accessed data has a long decoding latency. Two smart refresh schemes are proposed for this work: The first refresh scheme is designed to refresh long access latency data when it is accessed several times for access performance optimization; The second refresh scheme is designed to periodical detecting data with extremely long access latency and refreshing them for tail latency optimization. Experiment results show that the proposed schemes are able to significantly improve the tail latency and access performance with little overhead.

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.

Non-volatile memories (NVMs), such as phase change memory (PCM) and resistive random access memory (ReRAM), have emerged as promising memory technologies for replacements of DRAM due to their advantages, such as better scalability, zero cell leakage, and DRAM-comparable read latency. Furthermore, multiple level cell (MLC) NVMs offer high data density and memory capacity over single level cell (SLC) NVM-s. However, the adoption of MLC NVMs is limited by their high programming energy and latency as well as the low endurance. In this paper, we propose an enhanced (23}2/4 WOM code for ML-C NVMs, which exploits the asymmetric characteristic in MLC NVM cell state transitions. Unlike the conventional WOM codes that focus on eliminating the worst-case latency writes, we propose to enlarge the best-case latency writes in MLC NVM cell state transitions. After data shaping with the enhanced WOM code, proportion of the best-case latency writes is maximized. In this way, the enhanced WOM code simultaneously reduces energy and latency, and improves lifetime with no memory and logic overheads. Evaluations show exciting improvement from the proposed approach.

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.

Within SSDs, random access memory (RAM) has been adopted as cache inside controller for achieving better performance. However, due to the volatility characteristic of RAM, data loss may happen when sudden power interrupts. To solve this issue, capacitor has been equipped inside emerging SSDs as interim supplier. However, the aging issue of capacitor will result in capacitance decreases over time. Once the remaining capacitance is not able to write all dirty pages in the cache back to flash memory, data loss may happen. In order to solve the above issue, an efficient cache management scheme for capacitor equipped SSDs is proposed in this work. The basic idea of the scheme is to bound the number of dirty pages in cache within the capability of the capacitor. Simulation results show that the proposed scheme achieves encourage improvement on lifetime and performance while power interruption induced data loss is avoided.

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.

Solid state drives (SSDs) have been widely deployed in personal computers, data centers, and cloud storages. In order to improve performance, SSDs are usually constructed with a number of channels with each channel connecting to a number of nand flash chips, each flash chip consisting of multiple dies and each die containing multiple planes. Based on this parallel architecture, I/O requests are potentially able to access parallel units simultaneously. Despite the rich parallelism offered by the parallel architecture, recent studies show that the utilization of flash parallel units is seriously low. This paper shows that the low parallel unit utilization is highly caused by the access conflict among I/O requests. In this paper, we propose parallel issue queueing (PIQ), a novel I/O scheduler at the host systems. PIQ groups I/O requests without conflicts into the same batch and I/O requests with conflicts into different batches. Hence, the multiple I/O requests in one batch can be fulfilled simultaneously by exploiting the rich parallelism of SSDs. Extensive experimental results show that PIQ delivers significant performance improvement especially for the applications which have heavy access conflicts.

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.

Solid state drives (SSDs) are normally constructed with a number of parallel-accessible flash chips, where host I/O requests are processed in parallel. In addition, there are many internal activities in SSDs, such as garbage collection and wear leveling induced read, write, and erase operations, to solve the issues of inability of in-place updates and limited lifetime. When internal activities are triggered on a chip, the chip will be blocked. Our preliminary studies on several workloads show that when internal activities are frequently triggered, the host I/O performance will be significantly impacted because of the access conflict between them. In this work, in order to improve the access conflict induced performance degradation, a novel access conflict minimization scheme is proposed. The basic idea of the scheme is motivated by an interesting observation in SSDs: several chips are idle when other chips are busy with internal activities and host I/O requests. Based on this observation, we propose to schedule internal activities induced operations for minimized access conflict by exploiting the idleness of the multiple chips of SSDs. This approach is realized by two steps: First, read internal activities accessed data to the controller; second, by exploiting the idle chips during internal activities, write internal activities accessed data back to these idle chips. With this scheme, the internal activities can be processed with minimized access conflict to the host requests. Simulation results show that the proposed approach significantly reduces the access conflict, and in turn leads to a significant performance improvement of SSDs.

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.

ARM's big. LITTLE architecture coupled with Heterogeneous Multi-Processing (HMP) has enabled energy-efficient solutions in the dark silicon era. System-level techniques activate nonadjacent cores to eliminate chip thermal hotspot. However, it unexpectedly increases communication delay due to longer distance in network architectures, and in turn degrades application performance and system energy efficiency. In this paper, we present a novel hierarchical hardware-software collaborated approach to address the performance/temperature conflict in dark silicon many-core systems. Optimizations on interprocessor communication, application performance, chip temperature and energy consumption are well isolated and addressed in different phases. Evaluation results show that on average 22.57% reduction of communication latency, 23.04% improvement on energy efficiency and 6.11°C reduction of chip peak temperature are achieved compared with state-of-the-art techniques.

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.

To date, dynamic vehicle routing problem (DVRP) has attracted great research attentions due to its wide range of real world applications. In contrast to traditional static vehicle routing problem, the whole routing information in DVRP is usually unknown and obtained dynamically during the routing execution process. To solve DVRP, many heuristic and metaheuristic methods have been proposed in the literature. In this paper, we present a novel evolutionary search paradigm with learning capability for solving DVRP. In particular, we propose to capture the structured knowledge from optimized routing solution in early time slot, which can be further reused to bias the customer-vehicle assignment when dynamic occurs. By extending our previous research work, the learning of useful knowledge, and the scheduling of dynamic customer requests are detailed here. Further, to evaluate the efficacy of the proposed search paradigm, comprehensive empirical studies on 21 commonly used DVRP instances with diverse properties are also reported.

With the development of bit density and technology scaling, the process variation (PV) has become much severe on NAND flash memory. As PV presents reliability among flash blocks, which causes read performance variation to read data on different blocks. This paper proposes to improve read performance of LDPC based flash memory by exploiting the reliability characteristics of PV. First, a block grouping approach is proposed to classify the flash blocks based on their reliability. Then, a read data placement scheme is proposed, which is designed to place read-hot data on flash blocks with high reliability and move read-cold data to blocks with low reliability. Experiment results show that, with negligible overhead, the proposed scheme is able to significantly improve the read performance.

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.

Recent studies show that a multilevel cell flash cell in different states suffers from diverse error patterns in varying degrees. That is, the error rates of each page are highly dependent on the data content. Consequently, pages with different data will exhibit quite different error rates. However, existing technologies equipped with one uniform error correction code (ECC) scheme for all pages in a flash memory do not take the different error rates of pages into consideration. In this paper, we propose to exploit the asymmetric error rates of flash memory exhibited by the flash pages with different data for performance improvement. Before a page is programmed, its specific error rates, called content-dependent bit error rates (CDBERs), are estimated according to the content of the page. The margin between the CDBER of a page and the maximal error rates correctable by the uniform ECC code is exploited for performance improvement. On one hand, a faster and suitable write operation is selected to speed up the progress of programming while the increased speed induced CDBER does not exceed the maximal correctable error rates. On the other hand, a light-weight ECC scheme can be chosen for a faster read operation since the page decoding process of a light-weight ECC scheme incurs less time overhead. Finally, a state mapping scheme, which further reduces the CDBER through mapping high error rate states to the low error rate states of a page, is proposed. Simulation results show that the proposed approaches lead to significant write and read performance improvement.

Despite the great demand on and attempts at package express shipping services, online retailers have not yet had a practical solution to make such services profitable. In this paper, we propose an economical approach to express package delivery, i.e., exploiting relays of taxis with passengers to help transport package collectively, without degrading the quality of passenger services. Specifically, we propose a two-phase framework called crowddeliver for the package delivery path planning. In the first phase, we mine the historical taxi trajectory data offline to identify the shortest package delivery paths with estimated travel time given any Origin-Destination pairs. Using the paths and travel time as the reference, in the second phase we develop an online adaptive taxi scheduling algorithm to find the near-optimal delivery paths iteratively upon real-time requests and direct the package routing accordingly. Finally, we evaluate the two-phase framework using the real-world data sets, which consist of a point of interest, a road network, and the large-scale trajectory data, respectively, that are generated by 7614 taxis in a month in the city of Hangzhou, China. Results show that over 85% of packages can be delivered within 8 hours, with around 4.2 relays of taxis on average.

Dark silicon refers to the phenomenon that a fraction of a many-core chip has to become “dark” or “dim” in order to guarantee the system to be kept in a safe temperature range and allowable power budget. Techniques have been developed to selectively activate non-adjacent cores on many-core chip to avoid temperature hotspot, while resulting unexpected increase of communication overhead due to the longer average distance between active cores, and in turn affecting application performance and energy efficiency, when Network-on-Chip (NoC) is used as a scalable communication subsystem. To address the brand-new challenges brought by dark silicon, in this paper, we present FoToNoC, a Folded Torus-like NoC, coupled with a hierarchical management strategy for heterogeneous many-core systems. On top of it, objectives of maximizing application performance, energy efficiency and chip reliability are isolated and well achieved by hardware-software co-design in several different phases, including application mapping and scheduling, cluster management and DVFS control. Evaluations on PARSEC benchmark applications demonstrate the significance of the entire strategy. Compared with state-of-the-art approaches, the proposed FoToNoC organization can achieve on average 35.4 and 35.2 percent on communication efficiency and application performance improvement, respectively, when maintaining the safe chip temperature. The hierarchical cluster-based management strategy can further reduce an average 34.6 percent of the total energy consumption with a notable reduction on the chip peak temperature. The significant achievements on system energy efficiency and the reduction on chip temperature of H.264 decoder and DSP-stone benchmarks additionally verify the effectiveness of the proposed methods.

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.

Phase change memory (PCM) is a promising DRAM alternative because of its non-volatility, high density, low standby power and close-to-DRAM performance. These features make PCM an attractive solution to optimize the management of NAND flash memory in embedded systems. However, PCM's limited write endurance hinders its application in embedded systems. Therefore, how to manage flash memory with PCM-particularly guarantee PCM a reasonable lifetime-becomes a challenging issue. In this paper, we propose to partially replace DRAM using PCM to optimize the management of flash memory metadata for better system reliability in the presence of power failure and system crash. To prolong PCM's lifetime, we present a write-activity-aware PCM-assisted flash memory management scheme, called PCM-FTL. By differentiating sequential and random I/O behaviors, a novel two-level mapping mechanism and a customized wear-leveling scheme are developed to reduce writes to PCM and extend its lifetime. We evaluate PCM-FTL with a variety of general-purpose and mobile I/O workloads. Experimental results show that PCM-FTL can significantly reduce write activities and achieve an even distribution of writes in PCM with very low overhead.

Mobile applications are becoming increasingly feature-rich and powerful, but also dependent on large main memories, which consume a large portion of system energy, especially for devices equipped with 4/6 GB DRAM. Swapping inactive DRAM pages to byte-addressable, non-volatile memory (NVRAM) is a promising solution to this problem. However, most NVRAMs have limited write endurance and the current victim pages selecting algorithm does not aware it. Therefore, to make it practical, the design of an NVRAM based swapping system must also consider endurance. In this paper, we target at prolonging the lifetime of NVRAM based swap area in mobile devices by reducing the write activities to NVRAM based swap area. Different from traditional wisdom, such as wear leveling and hot/cold data identification, we propose to build a system called nCode, which exploits the fact that code pages are easy to identify, read-only, and therefore a perfect candidate for swapping. Utilizing NVRAM's byte-addressability, we support execute-in-place (XIP) of the code pages in the swap area, without copying them back to DRAM based main memory. Experimental results based on the Google Nexus 5 smartphone show that nCode can effectively prolong the lifetime of NVRAM under various workloads.

In this dark silicon era, techniques have been developed to selectively activate nonadjacent cores in physical locations to maintain the safe temperature and allowable power budget on a many-core chip. This will result in unexpected increase in the communication overhead due to longer average distance between active cores in a typical mesh-based Network-on-Chip (NoC), and in turn reduce the system performance and energy efficiency. In this paper, we present FoToNoC, a Folded Torus-like NoC, and a hierarchical management strategy on top of it, to address this tradeoff problem for heterogeneous many-core systems. Optimizations of chip temperature, inter-core communication, application performance, and system energy consumption are well isolated in FoToNoC, and addressed in different design phases and aspects. A cluster-based hierarchical strategy is proposed to manage the system adaptively in several different control levels. Compared with mesh-based systems on a set of synthetic and real benchmarks, FoToNoC can achieve on average 39.4% performance improvement when similar temperature conditions are maintained, and the proposed strategy can further reduce the total energy consumption by up to 42.0%.

Many emerging applications are inherently error-resilient and hence do not require exact computation. In this paper, we consider the task allocation and scheduling problem for mapping such applications to voltage-scalable multiprocessor systems. The proposed solution, namely ApproxMap, judiciously determines the mapping and execution sequence of resilient tasks to minimize the energy consumption of the application while meeting their target quality requirements and timing constraints. To be specific, ApproxMap generates energy-efficient yet flexible task schedule at design-time, and conducts lightweight online adjustment according to runtime dynamics for further energy-efficiency improvement. Experimental results on various task graphs demonstrate the efficacy of ApproxMap.

Memetic algorithms (MAs), which have materialized as a fusion of population based global search and individual lifetime learning (i.e., local search) in the literature, have been widely used in real world applications to solve complex optimization problems. The balance of global and local search in MA plays a key role in defining the performance of MA in problem solving. The probabilistic memetic framework (PMF) was thus introduced to model MA as a process involving the decision of embracing the separate actions of global or local search. PMF balances these two actions by governing the local search intensity of each individual based on a theoretical upper bound derived while the search progresses. To use PMF for solving combinatorial optimization problems, according to our previous study [1], we note that the appropriate selection of a distance metric for estimating the local search intensity is a critical role. Nevertheless, to the best of our knowledge, little or no research works in the literature has studied on suitable distance metric for PMF in the context of combinatorial optimization problems. In this paper, we attempt to fill this gap by presenting a preliminary study on the selection of distance metric in PMF for capacitated arc routing problem (CARP). In particular, we first analyze the suitability of 4 existing popular distance metrics used in combinatorial optimization for solving CARP. Subsequently a score based on closeness of neighborhood and fitness landscape correlation is proposed to quantify the suitability of a distance metric in estimating the local search intensity for PMF in the context of combinatorial optimization. Experimental study on 24 egl CARP benchmark instances highlighted the significance of choice of appropriate distance metric in PMF for solving combinatorial optimization problems, with 4 new best known CARP solutions established in the present study.

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.

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.

Virtualization offers significant benefits, such as better isolation and security for mobile systems. However, the limited amount of memory and virtualization's memory-demanding nature make it challenging to virtualize mobile systems efficiently. In this paper, we utilize morphable resistive memories to design a high-performance mobile system with an extensible memory space. With morphable resistive memories, a simple and effective page management technique, Balloonfish, is proposed to convert the memory cell state between multilevel and single-level for achieving a balance between performance and memory space. First, an application-specific page allocation is proposed for managing morphable resistive memories in virtualized mobile systems. Besides, we use a balloon-style algorithm to balance memory allocation among multiple virtual machines. Our evaluation based on the Samsung Exynos 5250 system-on-chip with various real Android applications shows that our system achieves 28.63% performance improvement compared with the baseline scheme.

NAND flash memory has been widely deployed in embedded systems, personal computers, and data centers. While recent technology scaling and density improvement have reduced its price, they have also significantly shortened its endurance. In this paper, with the understanding of the relationship between data retention time and flash wearing, a retention trimming approach, which trims data retention time based on the data lifetime, is proposed to reduce the wearing of flash memory, and hence improve the endurance of flash memory. Extensive experimental results show that the proposed technique achieves significant endurance improvements.

Smartphones are becoming increasingly energy-hungry to support feature-rich applications, posing a lot of pressure on battery lifetime and making energy consumption a non-negligible issue. In particular, dynamic random access memory (DRAM)-based main memory subsystem is a major contributor to the energy consumption of mobile devices. In this paper, we propose direct read (DR). Swap, an energy-efficient in-memory paging design to reduce energy consumption in smartphones. In DR. Swap, we adopt emerging energy-efficient nonvolatile memory (NVM) and use it as the swap area. Utilizing NVMs byte-addressability, we propose DR which guarantees zero memory copy for read-only requests when accessing a page in swap area. To better understand the energy consumption of swapping, we build an energy model to analyze the energy consumption of different paging architectures. We evaluate DR. Swap based on the Google Nexus 5 smartphone, experimental results show that our technique can reduce more than 50% energy consumption compared to DRAM backed swapping.

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.

The write performance of flash memory has been degraded significantly due to the recent density-oriented advancements of flash technology. Techniques have been proposed to improve the write performance by exploiting the varying strength of a flash block in its different worn-out stages. A block is written with a faster speed when it is new and strong, and gradually will be written with slower speeds as it is aging and becomes weak. Motivated by these works, this brief proposes a new technique by exploiting the significant process variation among flash blocks introduced by the advanced technology scaling. First, a write speed detection approach is proposed to identify the strength of each block. Then, a heuristic approach is proposed to exploit the speed variation among blocks for write performance improvement. A series of trace-driven simulations shows that the proposed approach generates substantial write performance improvement over state-of-the-art approaches by 30% on average.

Network-on-chip (NoC) is promising for the communication paradigm of the next-generation multiprocessor system-on-chip (MPSoC). As communication has become an integral part of on-chip computing, and even the performance bottleneck, researchers are paying much attention to its implementation and optimization. Traditional techniques that model communication inaccurately will lead to unexpected runtime performance, which is on average 90.8% worse than the predicted results based on observation, and are not suitable for the deep optimization of communication-intensive scenarios. In this paper, techniques are presented for the NoC-based MPSoCs that integrate optimization on interprocessor communications with the objective of minimizing the schedule length. A fine-grained integer-linear programming (ILP) model is proposed to properly address the communication latency with a network contention, which generates runtime scheduling with trivial performance difference from the predictions. We further propose a heuristic algorithm, unified priority-based scheduling (UPS), to effectively solve the contention problem in polynomial time by assigning priorities to messages. Evaluation results show that the solutions obtained by the ILP model outperform the state-of-the-art techniques by 31.1%, and UPS improves application performance by 34.7% and 44.4% compared with acquainted first-in-first-out (FIFO)-based and random-based methods. In addition, UPS achieves averagely 8.3% approximated results with the optimal solutions generated by ILP. A case study on H.264 high-definition television (HDTV) decoder and the digital signal processor (DSP) filter benchmarks achieves significant improvement on the performance and the results prediction accuracy, as well as the prominent reduction in the number of network contention and energy consumption.

Virtualization offers significant benefits such as better isolation and security for mobile systems. However, the limited amount of memory and virtualization's memory-demanding nature makes it challenging to virtualize mobile systems efficiently. In this paper, we utilize morphable resistive memories to design a high-performance mobile system with extensible memory space. With morphable resistive memory, we convert the memory cell state between multi-level and single-level to achieve a balance between performance and memory space. Our evaluation based on the Samsung Exynos 5250 SoC with real Android applications shows that our system achieve 27% performance improvement compared with the baseline scheme.

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.

Tasks in hard real-time systems are required to meet deadlines in the presence of faults. We conclude that a sufficient condition of a task set experiencing its worst-case finish time (WCFT) is that its critical task (CT) incurs all faults. An algorithm is presented to identify the CT and the WCFT in O(N2) with N being the task number. A common practice that bet the WCFT using the task with the longest re-execution time could under estimate by up-to 35%!

NAND flash memory has been widely applied in embedded systems, personal computer systems, and data centers. However, with the development of flash memory, including its technology scaling and density improvement, the endurance of flash memory becomes a bottleneck. In this work, with the understanding of the relationship between data retention time and flash wearing, a retention trimming approach, which trims data retention time based on the time intervals between data updating, is proposed to reduce the wearing of flash memory. Reduced wearing of flash memory will improve the endurance of the flash memory. Extensive experimental results show that the proposed technique achieves significant wearing reduction for flash memory through retention trimming.

Smartphones are getting increasingly high-performance with advances in mobile processors and larger main memories to support feature-rich applications. However, the storage subsystem has always been a prohibitive factor that slows down the pace of reaching even higher performance while maintaining good user experience. Despite today's smartphones are equipped with larger-than-ever main memories, they consume more energy and still run out of memory. But the slow NAND flash based storage vetoes the possibility of swapping---an important technique to extend main memory---and leaves a system that constantly terminates user applications under memory pressure.

The reliability of flash memory is getting worse with the introduction of Multiple Level Cell (MLC) and Triple Level Cell (TLC) technologies. To account for possible errors, each page in a flash memory is equipped with an Error Correction Code (ECC) module. An ECC scheme is chosen according to the worst-case error occurrences across all pages in the flash memory. Recent studies show that an MLC flash cell in different states exhibits diverse error rates and the difference is dramatic. Consequently, pages with different data will exhibit quite different error rates. Existing technologies that use one uniform ECC scheme for all pages in a flash memory is far from optimal. This paper exploits the asymmetric error rates exhibited by the pages with different data for write performance improvement. Before a page is programmed, its specific error rate, called Content-Dependent Bit Error Rate (CDBER), is estimated according to the content of the page. The margin between the CDBER of a page and the maximal error rate correctable by the uniform ECC code is exploited for write performance improvement. Simulation results show that the proposed approach leads to significant write performance improvement.

Smartphones are becoming increasingly energy-hungry to support feature-rich applications, posing a lot of pressure on battery lifetime and making energy consumption a non-negligible issue. In particular, DRAM is among the most demanding components in energy consumption. In this paper, we propose DR. Swap, an energy-efficient paging design to reduce energy consumption in smartphones. We adopt emerging energy-efficient non-volatile memory (NVM) and use it as the swap area. Utilizing NVM's byte-addressability, we propose direct read which guarantees zero-copy for read-only pages in the swap area. Experimental results based on the Google Nexus 5 smartphone show that our technique can effectively reduce energy consumption.

Solid state drives (SSDs) have been widely deployed in personal computers, data centers, and cloud storages. In order to improve performance, SSDs are usually constructed with a number of channels with each channel connecting to a number of NAND flash chips. Despite the rich parallelism offered by multiple channels and multiple chips per channel, recent studies show that the utilization of flash chips (i.e. the number of flash chips being accessed simultaneously) is seriously low. Our study shows that the low chip utilization is caused by the access conflict among I/O requests. In this work, we propose Parallel Issue Queuing (PIQ), a novel I/O scheduler at the host system, to minimize the access conflicts between I/O requests. The proposed PIQ schedules I/O requests without conflicts into the same batch and I/O requests with conflicts into different batches. Hence the multiple I/O requests in one batch can be fulfilled simultaneously by exploiting the rich parallelism of SSD. And because PIQ is implemented at the host side, it can take advantage of rich resource at host system such as main memory and CPU, which makes the overhead negligible. Extensive experimental results show that PIQ delivers significant performance improvement to the applications that have heavy access conflicts.

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.

Welcome to Chongqing, China, and the 20th IEEE International Conference on Embedded and Real- Time Computing Systems and Applications (RTCSA 2014). RTCSA has been a long-running technical conference sponsored by IEEE. The objective of the conference is to bring together academic researchers and industry developers for intensive discussion of recent advancing in the field of embedded systems, real-time systems, system design practice and emerging applications.

The performance of ad hoc networks depends on the cooperative and trust nature of the distributed nodes. To enhance security in ad hoc networks, it is important to evaluate the trustworthiness of other nodes without central authorities. An information‐theoretic framework is presented, to quantitatively measure trust and build a novel trust model (FAPtrust) with multiple trust decision factors. These decision factors are incorporated to reflect trust relationship's complexity and uncertainty in various angles. The weight of these factors is set up using fuzzy analytic hierarchy process theory based on entropy weight method, which makes the model has a better rationality. Moreover, the fuzzy logic rules prediction mechanism is adopted to update a node's trust for future decision‐making. As an application of this model, a novel reactive trust‐based multicast routing protocol is proposed. This new trusted protocol provides a flexible and feasible approach in routing decision‐making, taking into account both the trust constraint and the malicious node detection in multi‐agent systems. Comprehensive experiments have been conducted to evaluate the efficiency of trust model and multicast trust enhancement in the improvement of network interaction quality, trust dynamic adaptability, malicious node identification, attack resistance and enhancements of system's security.

In order to accelerate the convergence and improve the calculation accuracy for parameter optimization of the Muskingum model, we propose a novel, adaptive hybrid particle swarm optimization (AHPSO) algorithm. With the decreasing of inertial weight factor proposed, this method can gradually converge to a global optimal with elite individuals obtained by hybrid PSO. In the paper, we analyzed the feasibility and the advantages of the AHPSO algorithm. Then, we verified its efficiency and superiority by application of the Muskingum model. We intensively evaluated the error fitting degree based on the comparison with four known formulas: the test method (TM), the least residual square method (LRSM), the nonlinear programming method (NPM), and the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method. The results show that the AHPSO has a higher precision. In addition, we compared the AHPSO algorithm with the binary-encoded genetic algorithm (BGA), the Gray genetic algorithm (GGA), the Gray-encoded accelerating genetic algorithm (GAGA) and the particle swarm optimization (PSO), and results show that AHPSO has faster convergent speed. Moreover, AHPSO has a competitive advantage compared with the above eight methods in terms of robustness. With the efficiency of this approach it can be extended to estimate parameters of other dynamic models.

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.

Timely and efficient data dissemination is one of the fundamental requirements to enable innovative applications in vehicular cyber-physical systems (VCPS). In this work, we intensively analyze the characteristics of temporal data dissemination in VCPS. On this basis, we formulate the static and dynamic snapshot consistency requirements on serving real-time requests for temporal data items. Two online algorithms are proposed to enhance the system performance with different requirements. In particular, a reschedule mechanism is developed to make the scheduling adaptable to the dynamic snapshot consistency requirement. A comprehensive performance evaluation demonstrates the superiority of the proposed algorithms.

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.

The 0-1 knapsack problem is well known to be NP-complete problem. In the past two decades, much effort has been done in order to find techniques that could lead to algorithms with a reasonable running time. This paper proposes a new parallel algorithm for the 0-1 knapsack problem where the optimal merging algorithm is adopted. Based on an EREW PRAM machine with shared memory, the proposed algorithm utilizes O((2n/4)1-e) processors, 0 ≤ ε ≤ 1, and O(2n/2) memory to find a solution for the n-element 0-1 knapsack problem in time O(2n/4(2n/4)e). Thus the cost of the proposed parallel algorithm is O(2n/2), which is both the lowest upper-bound time and without memory conflicts if only quantity of objects is considered in the complexity analysis for the 0-1 knapsack problem. Thus it is an improvement result over the past researches.

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 high-level synthesis for real-time embedded systems using heterogeneous functional units (FUs), it is critical to select the best FU type for each task. However, some tasks may not have fixed execution times. This article models each varied execution time as a probabilistic random variable and solves the heterogeneous assignment with probability (HAP) problem. The solution of the HAP problem assigns a proper FU type to each task such that the total cost is minimized while the timing constraint is satisfied with a guaranteed confidence probability. The solutions to the HAP problem are useful for both hard real-time and soft real-time systems. Optimal algorithms are proposed to find the optimal solutions for the HAP problem when the input is a tree or a simple path. Two other algorithms, one is optimal and the other is near-optimal heuristic, are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost while satisfying timing constraints with guaranteed confidence probabilities. For example, our algorithms achieve an average reduction of 33.0% on total cost with 0.90 confidence probability satisfying timing constraints compared with the previous work using the worst-case scenario.

In this article, we focus on solving the energy optimization problem for real-time streaming applications on multiprocessor System-on-Chip by combining task-level coarse-grained software pipelining with DVS (Dynamic Voltage Scaling) and DPM (Dynamic Power Management) considering transition overhead, inter-core communication and discrete voltage levels. We propose a two-phase approach to solve the problem. In the first phase, we propose a coarse-grained task parallelization algorithm called RDAG to transform a periodic dependent task graph into a set of independent tasks by exploiting the periodic feature of streaming applications. In the second phase, we propose a scheduling algorithm, GeneS, to optimize energy consumption. GeneS is a genetic algorithm that can search and find the best schedule within the solution space generated by gene evolution. We conduct experiments with a set of benchmarks from E3S and TGFF. The experimental results show that our approach can achieve a 24.4% reduction in energy consumption on average compared with the previous work.

Energy-efficient and high-performance interconnections are critical for multiprocessor architectures. As technology moves into deep submicrometer level, static and dynamic energy consumptions have become dominant constraint factors in high-performance system design. This paper jointly considers scheduling and interconnection design to minimize the interconnection's energy consumption without performance degradation. The Interconnection Energy Minimization Scheduling algorithm is proposed in this paper to design interconnection with segmented buses and to determine a feasible computation and communication schedule to minimize interconnection's energy consumption while meeting tight-latency and high-volume data transfer needs for applications with large inherited parallelism. Experimental results show that interconnection's dynamic energy consumption can be reduced by about 71% and static energy consumption can be reduced by about 35% on average when the proposed algorithm is compared with existing communication cost-conscious scheduling techniques for the evaluated digital signal processing and media applications.

An MPSoC system usually consists of a number of processors, a memory hierarchy and a communication mechanism between processors. Because of the gap between the constantly increasing processor speed and slower memory access, how to utilize the memory subsystem more efficiently has become a critical issue for improving the overall system performance. To address this problem, two algorithms are proposed in this paper. The first one uses the integer linear programming method so that the memory access cost is minimized while tasks are scheduled in as short a time as possible. The second one is a heuristic algorithm which can achieve close to optimum results with linear running time. The experimental results show that the memory access cost can be reduced up to 56% comparing to LIST scheduling.

Energy efficient and high performance interconnect is critical for multi-core architecture. Interconnect with power saving segmented buses satisfies the tight latency and high volumn data transfer needs of applications with large embeded pallelism. This paper analyzes the major energy consumption factors of interconnect with segmented buses from high level synthesis. It presents a computation and inter-core data transfer scheduling algorithm to minimize the interconnect energy consumption by addressing the analyzed factors while exploring an application's maximum parallelism. This paper jointly considers scheduling and interconnect design. It presents an application specific approach to determine the minimum number of segmented buses required and an optimal inter core data transfer schedule which can be used to configure the switches on the segmented buses to avoid bus contention and minimize interconnect energy consumption with a given application. Experimental results show that the proposed scheduling algorithm can reduce interconnect dynamic about 23% on average compared to the other communication cost conscious scheduling techniques for evaluated high parallelism DSP applications.

Recent advances in circuit and process technologies have pushed non-volatile memory 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 computer systems. First, non-volatile memories have limited number of write/erase cycles compared with DRAM memory. Second, write activities on non-volatile memory are more expensive than DRAM memory in terms of energy consumption and access latency. Both challenges will benefit from reduction of the write activities on the nonvolatile memory.

Flash Memory is a desirable candidate for main memory replacement in embedded systems due to its low leakage power consumption, higher density and non-volatility characteristics. There are two challenges in applying flash memory as main memory. First, the write operations are much slower than read operations. Second, the lifetime of flash memory depends on the number of the write/erase operations. In this paper, we introduce a smart victim cache architecture to reduce the write activities by exploring the coarse grain accessing character of NAND flash memory. Experimental results show that the proposed approaches can reduce write activities on flash main memory by 65.38% on average compared to traditional architecture.

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%.

The widening gap between processor and memory performance is the main bottleneck for modern computer systems to achieve high processor utilization. To hide memory latency, a variety of techniques have been proposed—from intermediate fast memories (caches) to various prefetching and memory management techniques. In this article, we propose a new loop scheduling with memory management technique, Iterational Retiming with Partitioning (IRP), that can completely hide memory latencies for applications with multidimensional loops on architectures like CELL processor. In IRP, the iteration space is first partitioned carefully. Then a two-part schedule, consisting of processor and memory parts, is produced such that the execution time of the memory part never exceeds the execution time of the processor part. These two parts are executed simultaneously and complete memory latency hiding is reached. In this article, we prove that such optimal two-part schedule can always be achieved given the right partition size and shape. Experiments on DSP benchmarks show that IRP consistently produces optimal solutions as well as significant improvement over previous techniques.

With the shrinking of technology feature sizes, the share of leakage in total power consumption of digital systems continues to grow. Traditionaldynamic voltage scaling(DVS) fails to accurately address the impact of scaling on system power consumption as the leakage power increases exponentially. The combination of DVS andadaptive body biasing(ABB) is an effective technique to jointly optimize dynamic and leakage energy dissipation. In this paper, we propose an optimal soft real-time loop scheduling and voltage assignment algorithm,loop scheduling and voltage assignment to minimize energy, to minimize both dynamic and leakage energy via DVS and ABB. Voltage transition overhead has been considered in our approach. We conduct simulations on a set of digital signal processor benchmarks based on the power model of 70 nm technology. The simulation results show that our approach achieves significant energy saving compared to that of the integer linear programming approach.

High Instruction-Level-Parallelism in DSP and media applications demands highly clustered architecture. It is challenge to design an efficient, flexible yet cost saving interconnection network to satisfy the rapid increasing inter-cluster data transfer needs. This paper presents a computation and data transfer co-scheduling technique to minimize the number of partially connected interconnection buses required for a given embedded application while minimizing its schedule length. Previous researches in this area focused on scheduling computations to minimize the number of inter-cluster data transfers. The proposed co-scheduling technique in this paper not only schedules computations to reduce the number of inter-cluster data transfers, but also schedules intercluster data transfers to minimize the number of required partially connected buses for inter-cluster connection network. Experimental results indicate that 39.4% fewer buses required compared to current best known technique while achieving the same schedule length minimization.

According to the characteristics of the "3-D" structure of contemporary DRAM chips, the row first column ordered (RFCO) algorithm is proposed in this paper to minimize memory access schedule length. In memory systems with a single memory controller, assuming that the memory access trace is known before scheduling, the RFCO algorithm can generate schedules which are 7.89% shorter than burst scheduling on average. If memory accesses are coming to the single memory controller in real time, the RFCO algorithm can generate schedules which are 8.03% shorter than burst scheduling on average.

Many high-performance DSP processors employ multi-module on-chip memory to improve performance and power consumption. This paper studies the scheduling and assignment problem that minimizes the total energy while satisfying performance for applications with loops. An algorithm, LSAMEM (Loop Scheduling and Assignment to Minimize Energy for Memory), is proposed. The algorithm attempts to maximum energy saving while satisfying timing constraint with guaranteed probability. The experimental results show that the average improvement on energy-saving is significant by using LSAMEM.

In wireless sensor networks, the preloaded program code and data on sensor nodes often need to be updated due to changes in user requirements or environmental conditions. Sensor nodes are severely restricted by energy constraints. It is especially energy consuming for sensor nodes to update code through radio packages. To efficiently update code through wireless radio, we propose an algorithm, reprogramming with minimal transferred data (RMTD), to find the optimum combination of copying from the old code image and downloading from the host machine to minimize the number of bytes needed to be transferred from the host machine to a sensor node. Our experiments show that, for small code modifications, RMTD reduces the number of bytes transferred by 93.25% over the existing Rsync-based algorithm. For normal code changes, RMTD shows an improvement of 59.82% in average.

In high-level synthesis for real-time embedded systems using heterogeneous functional units (FUs), it is critical to select the best FU type for each task. However, some tasks may not have fixed execution times. This article models each varied execution time as a probabilistic random variable and solves heterogeneous assignment with probability (HAP) problem. The solution of the HAP problem assigns a proper FU type to each task such that the total cost is minimized while the timing constraint is satisfied with a guaranteed confidence probability. The solutions to the HAP problem are useful for both hard real-time and soft real-time systems. Optimal algorithms are proposed to find the optimal solutions for the HAP problem when the input is a tree or a simple path. Two other algorithms, one is optimal and the other is near-optimal heuristic, are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost while satisfying timing constraints with guaranteed confidence probabilities. For example, our algorithms achieve an average reduction of 33.0% on total cost with 0.90 confidence probability satisfying timing constraints compared with the previous work using worst-case scenario.

Loops are the most important sections for embedded applications. To achieve high performance, two loop transformation techniques are often applied, namely loop pipelining and loop partitioning, loop pipelining is an effective approach to increase parallelism and reduce schedule length. Loop partitioning with prefetching increases data locality and hides memory latency. However, loop pipelining increases register pressure and loop partitioning increases local memory requirement. As most embedded systems have limited number of registers and limited memory, without careful study, these two techniques can not be applied effectively. In this paper, we propose an effective scheduling framework, Register and Memory Sensitive Partition-ing(RMSP), to minimize average schedule length per iteration under register and memory dual constraints for parallel embedded systems. Experiments show that RMSP reduces schedule length by 14.1% in average compared to previous methods applied directly.

This paper studies the scheduling and assignment problem that minimizes the total energy including both dynamic and leakage energy for applications with loops on multi-voltage, multi-processor DSP. An algorithm, LSAMP (Loop Scheduling and Assignment to Minimize Power), is proposed. The algorithm attempts to minimize the total energy while satisfying timing constraint with guaranteed probability. We will perform scheduling and assignment simultaneously. Our approach shows better performance than the approach that considers scheduling and assignment at separate phases. Compared with previous work, our algorithm shows a significant improvement in total energy reduction.

Many high-performanceDSP processors employ multi-bank on-chip memory to improve performance and energy consumption. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to be executed in parallel. This paper studies the scheduling and assignment problem on minimizing the total energy consumption while satisfying timing constraint with heterogeneous multi-bank memory for applications with loop. An algorithm, TASL (Type Assignment and Scheduling for Loops), is proposed. The algorithm uses loop scheduling and assignment with the consideration of variable partition to find the best configuration for both memory and ALU.

Failure-Rate Minimization is becoming one of the major design issues in wireless sensor network (WSN) architecture due to multiple available Functional-units (FUs). There is a tradeoff between reliability and performance, such as timing constraint. This paper studies how to minimize the total failure rate while satisfying performance requirement for WSN applications. Two novel algorithms are proposed to solve the FRMFS (Failure Rate Minimization with FU Scheduling) problem. We use these FU scheduling algorithms to minimize system failure rate without sacrificing performance. Our results show that the average improvement on failure-rate reduction is significant with the use of our algorithms.

Multiple memory banks design is employed in many high performance DSP processors. This architectural feature supports higher memory bandwidth by allowing multiple data memory access to be executed in parallel. Dedicated address generation units (AGUs) are commonly presented in DSPs to perform address arithmetic in parallel to the main datapath. Address assignment, optimization of memory layout of program variables to reduce address arithmetic instruction, has been studied extensively on single memory architecture. Make effective use of AGUs on multiple memory banks is a great challenge to compiler design and has not been studied previously. In this paper, we exploit address assignment with variable partitioning for scheduling on DSP architectures with multiple memory banks and AGUs. Our approach is built on novel graph models which capture both parallelism and serialism demands. An efficient scheduling algorithm, Address Assignment Sensitive Variable Partitioning (AASVP), is proposed to best leverage both multiple memory banks and AGUs. Experimental results show significant improvement compare to existing methods.

Minimizing energy consumption is a key issue in designing real-time applications on wireless embedded systems. While a lot of work has been done to manage energy consumption on single processor real-time system, few work addresses network-wide energy consumption management for real-time tasks. Moreover, existing work on network-wide energy consumption assumes that the underlying network is always connected, which is not consistent with the practice in which wireless nodes often turn off their network interfaces in asleep schedule to reduce energy consumption. In this paper, we propose solutions to minimize network-wide energy consumption for real-time tasks with precedence constraints executing on wireless embedded systems. Our solutions take the radio sleep scheduling of wireless nodes into account when adjusting the execution modes of processors. We also propose a runtime dynamic energy management scheme to further reduce energy consumption while guaranteeing the timing constraint. The experiments show that our approach significantly reduces total energy consumption compared with the previous work.

In this paper, we develop a novel real-time instruction-level loop scheduling technique to reduce leakage energy consumption for applications with loops on VLIW architecture. We first prove that the scheduling problem with the minimum leakage energy consumption within a timing constraint is NP-complete. Then, LEMLS (leakage energy minimization loop scheduling) algorithm is designed to repeatedly regroup a loop based on rotation scheduling (Chao et al., 1997), and decrease leakage energy integrating with leakage power reduction mechanism. We conduct experiments on a set of DSP benchmarks based on the power model of the VLIW processors in (Liao et al., 2002). The results show that our algorithm achieves significant leakage energy saving compared with list scheduling and the algorithm in (You et al., 2006).

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.

This paper proposes a design exploration framework that considers impreciseness in design specification. In high-level synthesis, imprecise information is often encountered. Two types of impreciseness are considered, namely: 1) impreciseness underlying on functional unit specifications and 2) impreciseness due to system constraints, i.e., latency and register constraints. The framework is iterative and based on a core scheduling called "register-constrained inclusion scheduling." An example of how the scheduling algorithm works is shown. The effectiveness of the proposed framework for imprecise specification is demonstrated by exploring a design solution for three well-known benchmarks, namely: 1) discrete cosine transform; 2) Voltera filter; and 3) fast Fourier transform. The selected solution meets the acceptability criteria while minimizing the total number of registers

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.

Reducing address arithmetic instructions by optimization of address offset assignment greatly improves the performance of DSP applications. However, minimizing address operations alone may not directly reduce code size and schedule length for multiple functional units DSPs. In this paper, we exploit address assignment and scheduling for application with loops on multiple functional unit DSPs. Array transformation is used in our approach to leverage the indirect addressing modes provided by most of the DSP architectures. An algorithm, address instruction reduction loop scheduling (AIRLS), is proposed. The algorithm utilizes the techniques of rotation scheduling, address assignment and array transformation to minimize both address instructions and schedule length. Compared to the list scheduling, AIRLS shows an average reduction of 35.4% in schedule length and an average reduction of 38.3% in address instructions. Compared to the rotation scheduling, AIRLS shows an average reduction of 19.2% in schedule length and 39.5% in the number of address instructions.

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.

Increasing wire delays have become a serious problem for sophisticated VLSI designs. Clustered architecture offers a promising alternative to alleviate the problem. In the clustered architecture, the cache, register file and function units are all partitioned into clusters such that short CPU cycle time can be achieved. A key challenge is the arrangement of inter-cluster communication. In this paper, we present a novel algorithm for scheduling inter-cluster communication operations. Our algorithm achieves better register resource utilization than the previous methods. By judiciously putting the selected spilled variables into their corresponding consumer's local cache, the costly cross-cache transfer is minimized. Therefore, the distributed caches are used more efficiently and the register constraint can be satisfied without compromising the schedule performance. The experiments shows that our technique outperforms the existing cluster-oriented schedulers.

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.

Many computation-intensive or recursive applications commonly found in digital signal processing and image processing applications can be represented by data-flow graphs (DFGs). In our previous work, we proposed a new technique, extended retiming, which can be combined with minimal unfolding to transform a DFG into one which is rate-optimal. The result, however, is a DFG with split nodes, a concise representation for pipelined schedules. This model and the extraction of the pipelined schedule it represents have heretofore not been explored. In this paper, we demonstrate one scheduling algorithm for such graphs, and then discuss a way to reduce the hardware requirements of the resulting schedule. In the process, we state and prove a tight upper bound on the minimum number of processors required to execute the static schedule produced by our algorithms. Finally, we demonstrate our methods on a specific example.

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.

With the widening performance gap between processors and main memory, efficient memory accessing behavior is necessary for good program performance. Loop partition is an effective way to exploit the data locality. Traditional loop partition techniques, however, consider only a singleton nested loop. This paper presents multiple loop partition scheduling technique, which combines the loop partition and data padding to generate the detailed partition schedule. The computation and data prefetching are balanced in the partition schedule, such that the long memory latency can be hidden efficiently. Multiple loop partition scheduling explores parallelism among computations, and exploit the data locality between different loop nests as well in each loop nest. Data padding is applied in our technique to eliminate the cache interference, which overcomes the problem of cache conflict misses arisen from loop partition. Therefore, our technique can be applied in architectures with low associativity cache. The experiments show that multiple loop partition scheduling can achieve the significant improvement over the existing methods. 1.

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.

The paper proposes a scheme to tolerate the slow memory access latency for loop intensive applications in the system with memory hierarchy. The scheme takes into consideration of both the inter-mediate data and maximal overlap of data footprints for initial data. Furthermore, a schedule is presented to balance the ALU computa-tion and memory operations. The memory requirement under such schedule is calculated. This schedule’s improvement in total exe-cution time is approximately 20 % over existing methods. 1.

We present a scheme which explores the parallelism on a Java virtual machine (JVM). An algorithm, called dynamic-duplication scheduling is developed for solving the static scheduling and code generation for data flow graphs on the parallel JVM. Experimental results show that the schedule produced by the algorithm on the parallel JVM is significantly improved compared with the traditional JVM.

In system-level design of real-time embedded systems, being able to capture the interactions among the tasks with respect to timing constraints and determine the overall system timing performance is a major challenge. Most previous works in the area are either based on a fixed execution time model or are only concerned with the probabilistic timing behavior of each individual task. The few papers that deal with overall system probabilistic behavior have used improper assumptions. In this paper, given that the execution time of each task is a discrete random variable, a novel concept of state is introduced based on a new metric that is derived that measures the probability of a task set being able to be scheduled. Several approaches to evaluating the metric are also presented. Applying this metric in the system-level design exploration process, one can readily compare the probabilistic timing performance of alternative designs.

The large latency of memory accesses in modern computers is a key obstacle in achieving high processor utilization. To hide this latency, this paper proposes a new memory management technique that can be applied to computer architectures with three levels of memory. The technique takes advantage of access pattern information that is available at compile time by prefetching certain data elements from the higher level memory. It as well maintains certain data for a period of time to prevent unnecessary data swapping. Data locality is much improved compared with the usual pattern by partitioning the iteration space and reducing execution in each partition. These combined approaches lead to improvements in average execution times of approximately 35% over the one-level partition algorithm and more than 80% over list scheduling and hardware prefetching.

The trend in computer performance over the last 20 years has indicated that the memory performance constitutes a bottlneck for the overall system performance. As a result, smaller, faster memories have been introduced to hide the speed differential between the CPU and memory. From the beginning of this process, an essential question has been the determination of which part of main memory should reside in the faster memory at each instant. Several on-line and off-line algorithms have been introduced, the best known and most used of which are LRU and MIN respectively. This paper introduces a new approach to page replacement in that it allows the compiler to enter the decision process. In introducing compiler help to page replacement, information available at compile time is passed on to new hardware added to the regular memory, with the overall effect of markedly decreasing overall memory access time.

In this paper, we present an efficient approach to find effective module selections under resource, latency, and power constraints. The framework contains two phases: choosing a resource configuration, and determining a module binding for each resource. The first phase applies inclusion scheduling to estimate generic resources required. In the second phase, module utility measurement is used to determine module selections. A heuristic which perturbs module utility values until they lead to superior selections according to design objectives are also proposed. The experiments on well-known benchmarks show the effectiveness of the approach when comparing the obtained module selections with the results from enumerating all module selections, as well as MSSR and PSGA.

In high level synthesis, module selection, scheduling, and resource binding are interdependent tasks. For a selected module set, the best schedule/binding should be generated in order to accurately assess the quality of a module selection. Exhaustively enumerating all module selections and constructing a schedule and binding for each one of them can be extremely expensive. In this paper, we present an iterative framework, called WiZard to solve module selection problem under resource, latency, and power constraints. The framework associates a utility measure with each module. This measurement reects the usefulness of the module for a given a design goal. Using modules with high utility values should result in superior designs. We propose a heuristic which iteratively perturbs module utility values until they lead to good module selections. Our experiments show that by keeping modules with high utility values, WiZard can drastically reduce the module exploration space (approximately 99...

One of the difficulties in high-level synthesis and compiler optimization is obtaining a good schedule without knowing the exact computation time of the tasks involved. The uncertain computation times of these tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. The relationship between these tasks can be represented as a data-flow graph where each node models the task associated with a probabilistic computation time. A set of edges represents the dependencies between tasks. In this research, we study scheduling and optimization algorithms taking into account the probabilistic execution times. Two novel algorithms, called probabilistic retiming and probabilistic rotation scheduling, are developed for solving the underlying nonresource and resource constrained scheduling problems, respectively. Experimental results show that probabilistic retiming consistently produces a graph with a smaller longest path computation time for a given confidence level, as compared with the traditional retiming algorithm that assumes a fixed worst-case and average-case computation times. Furthermore, when considering the resource constraints and probabilistic environments, probabilistic rotation scheduling gives a schedule whose length is guaranteed to satisfy a given probability requirement. This schedule is better than schedules produced by other algorithms that consider worst-case and average-case scenarios.

In this paper, we present a design exploration framework, called WIZARD, which aims at finding module selections that will lead to superior designs while considering scheduling and resource binding under latency and power constraints. The framework contains two phases: choosing the resource configuration, and determining a module binding for each resource. We introduce a powerful model called an acceptability function which models design objectives, based on tradeoffs among different design constraints as well as a user's willingness to accept a design. Module utility measure cooperating with inclusion scheduling is the key to the success of our method. The utility of a module reflects the usefulness of the module based on the acceptability function. Inclusion scheduling is an algorithm to provide information for determining the number of functional units as well as module usefulness. We also present a heuristic which modifies module utility values based on the given acceptability function until they lead to superior selections. Many experiments on well-known benchmarks show the effectiveness of the approach when the obtained module selections are compared with the results from enumerating all module selections, as well as other schemes such as MSSR and PSGA.

In this paper, a method combining the loop pipelining technique with data prefetching, called Partition Scheduling with Prefetching (PSP), is proposed. In PSP, the iteration space is first divided into regular partitions. Then a two-part schedule, consisting of the ALU and memory parts, is produced and balanced to produce high throughput. These two parts are executed simultaneously, and hence, the remote memory latencies are overlapped. We study the optimal partition shape and size so that a well-balanced overall schedule can be obtained. Experiments on DSP benchmarks show that the proposed methodology consistently produces optimal or near optimal solutions.

This paper presents a novel approach to reducing the communication costs incurred when performing multiple multicasts on wormhole routed two-dimensional mesh multiprocessor systems. Both unicast and path-based implementations of multicasting incur communication costs due to the inherent message passing and contention for network resources. The start-up time dominates the transmission time when the data volume is small. However, in the presence of multiple multicasts when the data volume is very large, the communication delays due to message blocking and resource contention become very significant. Because of this, we present a hybrid static-dynamic technique to reduce the communication costs incurred when performing multiple multicasts on wormhole routed direct networks. This technique requires a focus on ordering and routing information for the individual message transmissions. At compile time, each message is assigned a priority using the recently developed collision graph model. Then at runtime these priorities are used to arbitrate the message transmissions. As a base, dimension-ordered routing is used. However, to further reduce the communication costs, some messages will be rerouted. This technique is useful either as a stand-alone algorithm or as an embedded procedure into existing algorithms. Furthermore, the techniques can be applied to higher dimension direct networks. For a single multicast, our work performs as well as conventional methods. For multiple multicasts, results show that our approach provides significant improvement over baseline techniques.

In this paper we present an iterative framework to solve module selection problem under resource, latency, and power constraints. The framework associates a utility measure with each module. This measurement reflects the usefulness of the module for a given a design goal. Using modules with high utility values will result in superior designs. We propose a heuristic which iteratively perturbs module utility values until they tend to good module selections. Our experiments show that the module selections formed by combinations of modules with high utility values are superior solutions. Further by keeping modules with high utility values, the module exploration space can drastically be reduced.

Many iterative or recursive applications commonly found in DSP and image processing applications can be represented by data-flow graphs (DFGs). This graph is then used to perform DFG scheduling, where the starting times for executing the application's individual tasks are determined. The minimum length of time required to execute all tasks once is called the schedule length of the DFG. A great deal of research has been done attempting to optimize such applications by applying various graph transformation techniques to the DFG in order to minimize this schedule length. One of the most effective of these techniques is retiming. We demonstrate that the traditional retiming technique does not always achieve optimal schedules and propose a new graph transformation technique, extended retiming, which will. We also present an algorithm for finding an extended retiming which transforms a DFG into one with minimal schedule length. Finally, we demonstrate a constant-time algorithm which verifies the existence of a retimed DFG with the minimum schedule length.

It is known that in many applications, because of selection statements, e.g., if-statement, the computation time of a node can be represented by a random variable. This paper focuses on any iterative application (containing loops) reflecting those uncertainties. Such an application can then be transformed to a probabilistic data-flow graph. A challenging problem is to derive graph transformation techniques which can produce a good schedule. This paper introduces two timing models, the time-invariant and time-variant models, to characterize the nature of these applications. Furthermore, for the time-invariant model, we propose a means of selecting a minimum rate-optimal unfolding factor which guarantees the best schedule length. We also propose a good estimation for choosing an unfolding factor for a graph under the time-variant model.

Many real time applications such as multimedia and DSP systems require high throughput, so it is necessary to have special purpose designs for them. Loop pipelining is an effective approach to reduce the total execution time of loops. While most previous research concentrates on the scheduling of computation, the experiments show that data access may give significant overhead if the register resource is limited. This paper studies the register constraint problem and presents Register Constrained Rotation Scheduling (RCRS), including the algorithm analyzing the number of required registers for loops and two classes of algorithms based on different assumptions. The first class is for loop scheduling with a given number of registers. If the number of registers is too stringent, the second class of algorithms are applied by inserting necessary LOAD/STORE operations into the loop schedule. Through the series of experiments, the RCRS algorithms are shown to achieve near optimal schedule length while satisfying register constraints.

The increasing demand for portable computing has elevated power consumption to be one of the most critical parameters for the execution of loops which constitute most of the computation of scientific applications. The reduction of a schedule length is usually considered to be opposite to the reduction of power. This paper presents a novel loop pipelining approach to reduce power consumption while reducing the schedule length. Power consumption is measured by transition activity between operands of successive operations. Both initial scheduling and loop scheduling across iterations try to reduce the transition activity at the inputs to the functional units. A series of experiments show that our method achieves considerable power dissipation and schedule length reduction.

Multidimensional (MD) systems are widely used to model scientific applications such as image processing, geophysical signal processing, and fluid dynamics. Such systems, usually, contain repetitive groups of operations represented by nested loops. The optimization of such loops, considering processing resource constraints, is required in order to improve their computational time. Most of the existing static scheduling mechanisms, used in the high-level synthesis of very large scale integration (VLSI) architectures, do not consider the parallelism inherent to the multidimensional characteristics of the problem. This paper explores the basic properties of MD loop pipelining and presents two novel techniques, multidimensional rotation scheduling and push-up scheduling, able to achieve the shortest possible schedule length. These new techniques transform a multidimensional data flow graph representing the problem, while assigning the loop operations to a schedule table. The multidimensional rotation scheduling is an iterative "heuristic" method, depending upon user input, while the push-up scheduling algorithm is able to compute the new schedule in polynomial time. The optimal resulting schedule length and the efficiency of the algorithms are demonstrated by a series of practical experiments.

One of the biggest problems in high-level synthesis is to obtain a good schedule without the knowledge of exact computation time of tasks. While the target applications in high-level synthesis are becoming larger a task in the applications such as artificial intelligent systems or interface may have uncertain computation time. In this paper an algorithm to schedule these repetitive tasks and optimize the schedule is presented. A probabilistic data-flow graph is employed to model the problem where each node represents a task associated with the probabilistic computation time and a set of edges represents the dependences between the tasks. A novel polynomial-time probabilistic retiming algorithm for optimizing the graph and an algorithm for computing the optimized schedule, subject to the acceptable probability and resource constraint, are presented. The optimization algorithm also guarantees to give such a short schedule length with a given qualitatively provable, confidence level. The experiments show that the resulting schedule length for a given confidence probability can be significantly reduced.

Multi-dimensional systems containing nested loops are widely used to model scientific applications such as image processing, geophysical signal processing and fluid dynamics. However, branches within these loops may degrade the performance of pipelined architectures. This paper presents the theory, supporting hardware and experiments of a novel technique, based on multi-dimensional retiming, for reducing pipeline hazards caused by branches within nested loops. This technique, called Multi-Dimensional Branch Anticipation Scheduling, is able to achieve near-optimal schedule length for nested loops containing branch instructions.

This paper proposes an algorithm called probabilistic rotation scheduling which takes advantage of loop pipelining to schedule tasks with uncertain times to a parallel processing system. These tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. We show that based on our loop scheduling algorithm the length of the resulting schedule can be guaranteed to be satisfied for a given probability. The experiments show that the resulting schedule length for a given probability of confidence can be significantly better than the schedules obtained by worst-case or average-case scenario.

We consider the resource-constrained scheduling of loops with interiteration dependencies. A loop is modeled as a data flow graph (DFG), where edges are labeled with the number of iterations between dependencies. We design a novel and flexible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining. The rotation technique repeatedly transforms a schedule to a more compact schedule. We provide a theoretical basis for the operations based on retiming. We propose two heuristics to perform rotation scheduling and give experimental results showing that they have very good performance.

This paper presents a novel optimization technique for the design of application specific integrated circuits dedicated to perform iterative or recursive time-critical sections of multidimensional problems, such as image processing applications. These sections are modeled as cyclic multidimensional data flow graphs (MDFGs). This new optimization technique, called multidimensional interleaving, consists of a multidimensional expansion and compression of the iteration space, followed by a multidimensional retiming, while considering memory requirements. It guarantees that all functional elements of a circuit can be executed simultaneously, and no additional memory queues proportional to the problem size are required. The algorithm runs optimally in O(|E|) time, where E is the set of edges of the MDFG representing the circuit. Our experiments show that the additional memory requirement is significantly less than the results obtained in other methods.

Loop scheduling is an important problem in parallel processing. The retiming technique reorganizes an iteration; the unfolding technique schedules several iterations together. We combine these two techniques to obtain a static schedule with a reduced average computation time per iteration. We first prove that the order of retiming and unfolding is immaterial for scheduling a data-flow graph (DFG). From this nice property, we present a polynomial-time algorithm on the original DFG, before unfolding, to find the minimum-rate static schedule for a given unfolding factor. For the case of a unit-time DFG, efficient checking and retiming algorithms are presented.

In applications requiring very high throughput or which have real-time deadlines, the use of parallel processing techniques has become widespread. Although there exists potential for vast performance gains, the communication overhead inherent in such systems can significantly lessen these gains. In this paper, with tightly-coupled architectures as the platform, the static communication scheduling of messages in the network is addressed. The compile time determination of when nodes should send their messages to other nodes is what is termed static communication scheduling. In parallel systems the static scheduling of computational tasks has been studied for some time, however an in depth analysis of our problem is very new. This paper builds a framework based on the newly developed collision graph model. Using this model, the determination of an optimal schedule is proven to be NP-Complete. Several efficient algorithms are designed to deal with a general case model of message traffic, and experiments show a significant improvement over baseline approaches.

One of the common problems for fuzzy system implementation arises from the complications of the fuzzy inference process. Extra computations are required to deduce a consequence due to nature of fuzzy sets. Furthermore, considerable simulations need to be performed to verify system functions. In order to reduce the prototyping time, the fuzzy system is partitioned into hardware and software portions. The model, called Fuzzy Rule-based Automata (FRA), is proposed to simplify fuzzy rule base. Since most rule base are rarely changed, they can be implemented in hardware to speedup the running time. Special computations for inference process is taken care by software to reduce hardware complications which yields prototype flexibility.

The novel optimization technique for the design of application specific integrated circuits of multi-dimensional problems, called multi-dimensional interleaving consists of an expansion and compression of the iteration space. It guarantees that all functional elements of a circuitry can be executed simultaneously, and no additional memory queues proportional to the problem size are required. Such technique, that considers the parallelism inherent to multi-dimensional problems, depend on loop transformations that require a new execution sequence of the loop. This study presents a new approach on synthesizing multidimensional (nested) loops, where pre-processor tools can rewrite the instructions in such a way to accommodate the required changes in the optimized design. This new approach is expected to improve the design cycle by including multidimensional signal processing and other common applications in the scope of the synthesis tools.

The design of computer systems that incorporate both standardized off-the-shelf processors, or software, as well as specialized hardware is referred to as hardware/software (hw/sw) co-design. This paper studies the problem and presents a system, the Hardware/MultiSoftware Co-design (HMS) system, for obtaining the best hw/sw configuration for DSP applications. New algorithms for performing partitioning, scheduling, loop pipelining (retiming), hardware needability analysis, etc., are presented. The final configuration satisfies both area and time constraints while using as many standardized processors as possible along with a minimum amount of extra hardware.

While research on the static scheduling of computational tasks for parallel systems has been ongoing for years, most work does not consider the communication costs nor does it consider the network congestion. A new static scheduling technique is presented which focuses on the communication overhead inherent in parallel processing systems. This paper builds a framework based on a newly developed graph model called a collision graph to study this problem. Using this model, algorithms are developed which can be embedded into existing static scheduling methods to improve their performance. The scheduling of cyclic data flow graphs was shown to be improved significantly as this technique was applied to the cyclo-compaction scheduling algorithm.

The VHDL language is considered to be an important standard among the hardware description tools. Most of the existing loop optimization techniques that consider the parallelism inherent to multi-dimensional problems depend on loop transformations not available in the current VHDL Synthesis products. This study presents a coding technique on modeling multi-dimensional (nested) loops on VHDL, where pre-processor tools can rewrite the VHDL instructions in such a way that the optimized design can be synthesized. This new approach is expected to improve the VHDL design cycle by including multidimensional signal processing and other common applications in the scope of the VHDL Synthesis tools.

Uniform nested loops are broadly used in scientific and multidimensional digital signal processing applications. Due to the amount of data handled by such applications, on-chip memory is required to improve the data access and overall system performance. In this study a static data scheduling method, carrot-hole data scheduling, is proposed for multidimensional applications, in order to control the data traffic between different levels of memory. Based on this data schedule, optimal partitioning and scheduling are selected. Experiments show that by using this technique, on-chip memory misses are significantly reduced as compared to results obtained from traditional methods. The carrot-hole data scheduling method is proven to obtain smallest on-chip memory misses compared with other linear scheduling and partitioning schemes.

Most scientific and digital signal processing (DSP) applications are recursive or iterative. Transformation techniques are usually applied to get optimal execution rates in parallel and/or pipeline systems. The retiming technique is a common and valuable transformation tool in one-dimensional problems, when loops are represented by data flow graphs (DFGs). In this paper, uniform nested loops are modeled as multidimensional data flow graphs (MDFGs). Full parallelism of the loop body, i.e., all nodes in the MDFG executed in parallel, substantially decreases the overall computation time. It is well known that, for one-dimensional DFGs, retiming can not always achieve full parallelism. Other existing optimization techniques for nested loops also can not always achieve full parallelism. This paper shows an important and counter-intuitive result, which proves that we can always obtain full-parallelism for MDFGs with more than one dimension. This result is obtained by transforming the MDFG into a new structure. The restructuring process is based on a multidimensional retiming technique. The theory and two algorithms to obtain full parallelism are presented in this paper. Examples of optimization of nested loops and digital signal processing designs are shown to demonstrate the effectiveness of the algorithms.

This paper considers several different algorithms that reduce the required number of buses for multi-chip module design. An efficient polynomial time algorithm that calculates the minimum number of buses needed given a particular schedule is presented. We also present three algorithms that minimize the number of buses during scheduling. Experimental results are shown that illustrate the efficiency of the algorithms.

While self-timed pipelines have overcome the problem of clock skew which degrades the performance of synchronous pipelines, the improvement is not without its cost; self-timed pipelines are forced to spend a larger amount of time on communication than their synchronous counterparts. This has led researchers to search for ways to improve the performance of self-timed pipelines by changing the communication scheme in an effort to reduce the communication delay. Our approach divides the total communication time into two parts: data communication delay and pace handshaking overhead. By adding buffer loops to each stage of a self-timed pipeline, we can reduce the pace handshaking overhead; thus decreasing the total time spent on communication. One important result of this design innovation has been the simplification of analysis needed to find the best initial system configuration. With our design, the same initial system configuration may be chosen regardless of computation time and variations in computation time. In addition, our design has a lower average cycle time than the traditional self-timed pipeline, which leads to an increase in performance.

In order to realize DSP applications on multiprocessor systems with the optimal throughput, the properties and efficient techniques need to be derived. Rate-optimal scheduling with minimum unfolding has been studied in the past for static schedules only. The scheduling models called cyclo-static and periodic schedules allow more flexibility in processor assignment. This paper derives the minimum unfolding factors required to achieve rate-optimal schedules for cyclo-static and periodic schedules. The necessary and sufficient conditions for the existence of these schedules are also derived. From these results, it is shown that unfolding is necessary under these two models for certain data flow graphs to achieve rate-optimality. Furthermore, all the theorems are proved in a constructive way, in which an efficient shortest-path algorithm is used for scheduling.

Two-dimensional filters are commonly used in digital image processing applications. These filters have the characteristic of processing recursive sets of instructions requiring high computational speed. These sets are modeled as cyclic two-dimensional data flow graphs, which are also used to represent the equivalent circuit design. In this new method, such graphs are submitted to a multi-dimensional retiming in order to reduce their cycle time. Such a reduction can achieve a cycle equal to the longest atomic operation in the filter, by inserting a fixed number of registers, independent of the size of the problem, into the circuit paths. Examples, a description and the correctness of our algorithm are presented.

Multi-dimensional computing applications, such as image processing and fluid dynamics, usually contain repetitive groups of operations represented by nested loops. The optimization of such loops, considering processing resource constraints, is required to improve their computational time. This study presents a new technique, called push-up scheduling, able to achieve the shortest possible schedule length in polynomial time. Such technique transforms a multi-dimensional dataflow graph representing the problem, while assigning the loop operations to a schedule table in such a way to occupy, legally, any empty spot. The algorithm runs in O(n|E|) time where n is the number of dimensions of the problem, and |E| is the number of edges in the graph.

This paper presents a novel optimization technique for the design of application specific integrated circuits dedicated to perform iterative or recursive time-critical sections of multi-dimensional problems, such as image processing applications. These sections are modeled as cyclic multi-dimensional data flow graphs (MDFGs). This new technique, called multi-dimensional interleaving consists of an expansion and compression of the iteration space while considering memory requirements. It guarantees that all functional elements of a circuitry can be executed simultaneously, and no additional memory queues proportional to the problem size are required. The algorithm runs in O(|E|) time, where E is the set of edges of the MDFG representing the circuit.

Multi-dimensi onal (MD) systems are widely used in scienti c applications such as image processing, geophysical signal processing and uid dynamics.Earlier scheduling methods in synthesizing MD systems do not explore loop pipelinin g across dierent dimensions.This paper explores the basic properties of MD loop pipelini ng and presents an algorithm, called multi-dimensional r otation scheduling, to nd an ecient s c hedule based on the multi-dimensional retiming technique we developed.The description and the correctness of our algorithm are presented in the paper.The experiments show that our algorithm can achieve optimal results ecien tly.

Loop pipelining (retiming) is a valuable tool used to explore parallelism across iterations. Few results are available about loop pipelining with data communication considerations. This paper first designs a modified list scheduling algorithm to be used as a subroutine in a novel technique called "communication sensitive rotation scheduling". Such a technique explores loop pipelining properties while handling the underlying imposed communication environment. An initial schedule is transformed to a more compact one under resource constraints.>

Most scientific and DSP applications are recursive or iterative. Uniform nested loops can be modeled as multi-dimensional data flow graphs (DFGs). To achieve full parallelism of the loop body, i.e., all the computational nodes executed in parallel, substantially decreases the overall computation time. It is well known that for one-dimensional DFGs retiming can not always achieve full parallelism. This paper shows an important and counter-intuitive result, which proves that we can always obtain full-parallelism for DFGs with more than one dimension. It also presents two novel multi-dimensional retiming techniques to obtain full parallelism.

Retiming and clock skew are both timing optimization methods for synchronous circuitry but are usually applied separately. We use the concept of scheduling to form a common background in the formulation of retiming and clock skew, and to study the interplay between, retiming and clock skew. A methodology to optimise synchronous circuitry with both retiming and clock skew is proposed.>

The use of massive parallelism in solving Partial Differential Equations (PDEs) has been studied for a long time. Fettweis and Nitache (1991) introduced a new method of transforming a PDE problem in a set of computational nodes represented by wave digital filters working in a multidimensional environment. Those computational nodes may not be mapped one-to-one to processor elements. After the nodes are partitioned into blocks, this paper introduces the concept of transforming such blocks to multidimensional data flow graphs, and an algorithm to obtain a final execution schedule with an optimal performance by using multidimensional retiming. The method is applicable to any uniformly represented data dependence graph and the Fettweis and Nitache method was chosen as an interesting example of its application.>

We consider the resource-constrained scheduling of loops with inter-iteration dependencies.A loop is modeled as a data flow graph (DFG), where edges are labeled with the number oj iterations between dependencies.We design a novel and ji'exible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining.The rotation technique repeatedly transforms a schedule to a more compact schedule.We provide a theoretical basis for the operations based on retiming.We propose two heuristics to perform rotation scheduling, and give experimental results showing that they have very good performance.

It is shown how to find a rate-optimal static schedule with the minimum unfolding factor under two design approaches: pipelined hardware design and nonpipelined hardware design. For pipelined hardware design, the technique also can be applied to so-called software pipelining in parallel compilers. It is shown that the minimum unfolding factor to achieve a rate-optimal schedule is the denominator rho of the irreducible form of B(G). After the minimum rate-optimal unfolding factor is derived from the iteration bound B(G) in time O( mod V//E mod log mod V mod ), a retiming to achieve the rate-optimal schedule in time O( mod V//E mod ) can be obtained. The rate-optimal schedule is then computed from the retiming. The minimum rate-optimal unfolding factor for nonpipelined design is also found.>

Given a behavioral description of an algorithm represented by a data-flow graph, we show how to obtain a rote-optimal static schedule with the minimum unfolding factor under two timing models, integral grid model and fractional grid model, and two design styles for each model, pipelined design and non-piplined design. We present a simple and unified approach to deal with the four possible combinations. A unified polynomial-time scheduling algorithm is presented, which works on the original data-flow graphs without really unfolding. The values of the minimum rate-optimal unfolding factors for all the four combinations are also derived.

Abstract We present an on‐line distributed reconfiguration algorithm for finding a new maximum matching incrementally after some nodes have failed. Our algorithm is deadlock‐free and, withkfailures, maintains at leastM–kmatching pairs during the reconfiguration process, whereMis the size of the original maximum matching. The algorithm tolerates failures that occur during reconfiguration. The worst‐case reconfiguration time isO(kmin(|A|, |B|)) afterkfailures, whereAandBare the node sets, but simulations show that the average‐case reconfiguration time is much better. The algorithm is also simple enough to be implemented in hardware. ©1993 by John Wiley & Sons, Inc.

The authors study fault-tolerant redundant structures for maintaining reliable arrays. In particular, they assume that the desired array (application graph) is embedded in a certain class of regular, bounded-degree graphs called dynamic graphs. The degree of reconfigurability (DR) and DR with distance (DR/sup d/) of a redundant graph are defined. When DR and DR/sup d/ are independent of the size of the application graph, the graph is finitely reconfigurable (FR) and locally reconfigurable (LR), respectively. It is shown that DR provides a natural lower bound on the time complexity of any distributed reconfiguration algorithm and that there is no difference between being FR and LR on dynamic graphs. It is also shown that if both local reconfigurability and a fixed level of reliability are to be maintained, a dynamic graph must be of a dimension at least one greater than the application graph. Thus, for example, a one-dimensional systolic array cannot be embedded in a one-dimensional dynamic graph without sacrificing either reliability or locality of reconfiguration.>

Retiming and unfolding are two useful techniques which have been effectively applied in many fields. These two techniques are combined to solve the problem of rate-optimal scheduling for unit-time data flow graphs (DFGs). A rate-optimal retimeable graph is a DFG such that after a legal retiming a rate-optimal schedule can be obtained. For the case of unit-time DFG, which is applicable to RISC multiprocessors, the best known upper-bound for an unfolding factor which produces a rate-optimal retimeable DFG is improved, and it is shown that the result is the minimum possible unfolding factor for rate-optimal schedules. Moreover, for any unfolding factor, the corresponding minimum rate is given by a simple criterion. Since it is proved that the order of retiming and unfolding is irrelevant, efficient polynomial-time retiming algorithms are obtained.>

ITRED (input-driven time-redundancy error detection), a methodology based on dependency graphs for doing concurrent run-time error detection in systolic arrays and wavefront processors, is described. It combines the projection method of deriving systolic arrays from dependency graphs with the idea of input-triggered testing. Tests are triggered by inserting special symbols in the input, and so the approach gives the user flexibility in trading off throughput for error coverage. Correctness of timing is proved at the dependency graph level. The method requires no extra processing elements and little extra hardware. The general approach is presented, and corresponding constraints on the modified dependency graphs that guarantee correctness are derived.>

Fault-tolerant redundant structures for maintaining reliable arrays are studied. It is assumed that the desired array (application graph) is embedded in a certain class of regular, bounded-degree graphs called dynamic graphs. The authors define the degree of reconfigurability (DR), and DR with distance DR/sup d/ of a redundant graph. When DR (respectively DR/sup d/) is independent of the size of the application graph, it is said that the graph is finitely reconfigurable, FR (resp. locally reconfigurable, LR). It is shown that DR provides a natural lower bound on the time complexity of any distributed reconfiguration algorithm, and that there is no difference between being FR and LR on dynamic graphs. It is then shown that if one wishes to maintain both local reconfigurability and a fixed level of reliability, a dynamic graph must be of dimension at least one greater than the application graph.>

It has been noted that arbitrary test pairs ( nu /sub 1/, nu /sub 2/) cannot be applied to a combinational pair of a finite state machine using standard scan path design. The scan path design is a special case of test machines which are designed to control and observe the object machine for detecting faults. By studying state transition graphs, the authors propose a general framework, which is composed of two stages, to solve this problem. Given a set of test pairs and a set of test machines, the first stage is to select a test machine which has the maximum delay fault coverage. If the fault coverage is not satisfactory, two approaches are proposed at the second stage. It is shown that these two optimization problems in the second stage are both NP-hard. Three algorithms are designed to solve these problems.>