Data movement between memory subsystem and processor unit is a crippling performance and energy bottleneck for data-intensive applications. Near Memory Processing (NMP) is a promising solution to alleviate the data movement bottleneck. The introduction of 3D-stacked memories and more importantly hybrid memory systems enable the long-wished NMP capability. This work explores the feasibility and efficacy of having NMP on the hybrid memory system for a given set of applications. In this paper, we first redefine a set of NMP-centric performance metrics in order to analyze the efficacy of a given processing unit. Leveraging the proposed metrics, we characterize various sets of applications to assess the suitability of a processing unit in terms of performance. Specifically, in this work we motivate the efficiency of NMP subsystems to process memory-intensive applications when 3D-NVM technologies are employed.

Fused CPU-GPU architectures that utilize the powerful features of both processors are common nowadays. Using homogeneous interconnect for such heterogeneous processors can result in performance degradation and power increase. This paper explores the optimization of heterogeneous NoC design to connect heterogeneous CPU-GPU architecture in terms of NoC performance and power. This involves solving four different NoC design sub-problems simultaneously; processing elements (PEs) mapping, buffer size and virtual channel assignments, and links' bandwidth determination. Heuristic-based optimization methods were proposed to obtain a near-optimal heterogeneous NoC design, and formal models were used to get a measure of the NoC performance and power of the evaluated design. The obtained optimal designs were validated using a full-system simulator.

As recent neural networks are being improved to be more accurate, their model's size is exponentially growing. Thus, a huge number of parameters requires to be loaded and stored from/in memory hierarchy and computed in processors to perform training or inference phase of neural network processing. Increasing the number of parameters causes a big challenge for real-time deployment since the memory bandwidth improvement's trend cannot keep up with models' complexity growing trend. Although some operations in neural networks processing are computational intensive such as convolutional layer computing, computing dense layers face with memory bandwidth bottleneck. To address the issue, the paper has proposed Partition Pruning for dense layers to reduce the required parameters while taking into consideration parallelization. We evaluated the performance and energy consumption of parallel inference of partitioned models, which showed a 7.72× speedup of performance and a 2.73× reduction in the energy used for computing pruned fully connected layers in TinyVGG16 model in comparison to running the unpruned model on a single accelerator. Besides, our method showed a limited reduction in accuracy while partitioning fully connected layers.

Summary The divisible load scheduling of image processing applications on the heterogeneous star and multi‐level tree networks is addressed in this paper. In our platforms, processors and network links have different speeds. In addition, computation and communication overheads are considered. A new genetic algorithm for minimizing the processing time of low‐level image applications using divisible load theory is introduced. The closed‐form solution for the processing time, the image fractions that should be allocated to each processor, the optimum number of participating processors, and the optimal sequence for load distribution are derived. The new concept of equivalent processor in tree network is introduced and the effect of different image and kernel sizes on processing time and speed up are investigated. Finally, to indicate the efficiency of our algorithm, several numerical experiments are presented.

Deep neural networks are widely used in many artificial intelligence applications. They have demonstrated state-of-the-art accuracy on many artificial intelligence tasks. For this high accuracy to occur, deep neural networks require the right parameter values. This is achieved by a process known as training . The training of large amounts of data via many iterations comes at a high cost in regard to computation time and energy. Optimal resource allocation would therefore reduce the training time. TensorFlow, a computational graph library developed by Google, alleviates the development of neural network models and provides the means to train these networks. In this article, we propose Adaptive HTF-MPR to carry out the resource allocation, or mapping, on TensorFlow. Adaptive HTF-MPR searches for the best mapping in a hybrid approach. We applied the proposed methodology on two well-known image classifiers: VGG-16 and AlexNet. We also performed a full analysis of the solution space of MNIST Softmax. Our results demonstrate that Adaptive HTF-MPR outperforms the default homogeneous TensorFlow mapping. In addition to the speed up, Adaptive HTF-MPR can react to changes in the state of the system and adjust to an improved mapping.

This paper proposes a cost-efficient approximate logarithmic multiplication for convolutional neural networks (CNNs), where two truncated logarithmic multipliers are connected for error correction. The proposed iterative logarithmic multiplication achieves low and unbiased average error while the hardware cost is significantly reduced by utilizing the truncated Mitchell multiplier and approximating error terms from the first stage. The proposed design has error characteristics that are suitable for neural network inferences, and the experiments on contemporary CNNs show that the proposed multiplier does not cause significant degradation on accuracy compared to exact multiplication.

Heterogeneous computing architectures that fuse both CPU and GPU on the same chip are common nowadays. Using homogeneous interconnect for such heterogeneous processors each with different network demands can result in performance degradation. In this paper, we focused on designing a heterogeneous mesh-style network-on-chip (NoC) to connect heterogeneous CPU-GPU processors. We tackled three problems at once; mapping Processing Elements (PEs) to the routers of the mesh, assigning the number of virtual channels (VC), and assigning the buffer size (BS) for each port of each router in the NoC. By relying on formal models, we developed a method based on Strength Pareto Evolutionary Algorithm2 (SPEA2) to obtain the Pareto optimal set that optimizes communication performance and power consumption of the NoC. By validating our method on a full-system simulator, results show that the NoC performance can be improved by 17% while minimizing the power consumption by at least 2.3x and maintaining the overall system performance.

Spin transfer torque (STT-RAM) is a fast, scalable and non-volatile memory technology. These characteristics make STT-RAM one of the best candidates among memories that can be used for space applications. Although STT-RAM cell itself is immune to high energy particles, its sensing circuit might be severely affected by radiation. In this work, we first extensively analyze the effect of radiation on the STT-RAM sense circuit and then propose a radiation hardened circuit. Using a dual modular redundancy and a voting scheme, radiation susceptibility of the sense circuit is eliminated. The sense circuit is implemented in 45 nm CMOS technology. Simulation results show that the proposed circuit is immune to radiation pulses up to 400 Krad.

Convolutional neural networks have been proposed as an approach for classifying data corresponding to labeled and unlabeled datasets. The fast-growing data empowers deep learning algorithms to achieve higher accuracy. Numerous trained models have been proposed, which involve complex algorithms and increasing network depth. The main challenges of implementing deep convolutional neural networks are high energy consumption, high on-chip and off-chip bandwidth requirements, and large memory footprint. Different types of on-chip communication networks and traffic distribution methods have been proposed to reduce memory access latency and energy consumption of data movement. This paper proposes a new traffic distribution mechanism on a mesh topology using distributer nodes by considering memory access mechanism in the AlexNet, VggNet, and GoogleNet trained models. We also propose a flow mapping method (FMM) based on dataflow stationary which reduces energy consumption by 8%.

Cloud applications are increasingly playing a crucial role in big data analytics. New use cases such as autonomous cars and edge computing call for novel approaches mixing heterogeneous computing and machine learning. These applications typically process petabyte-scale datasets, therefore, requiring low-power and scalable storage providing low-latency and high-throughput data access. While data centers have been focusing on migrating from legacy HDDs and SATA SSDs by deploying high-throughput and low-latency NVMe SSDs, the data bottlenecks appear as capacity scales. One approach to tackle this problem is to enable processing to happen within the storage device -in-storage processing (ISP)- eliminating the need to move the data. In this paper, we investigated the deployment of storage units with embedded low-power application processors along with FPGA-based reconfigurable hardware accelerators to address both performance and energy efficiency. To this purpose, we developed a high-capacity solid-state drive (SSD) named Catalina equipped with a quad-core ARM A53 processor running a Linux operating system along with a highly efficient FPGA accelerator for running applications in-place. We evaluated our proposed approach on a case study application for a similarity search library called Faiss.

This paper proposes energy-efficient approximate multipliers based on the Mitchell’s log multiplication, optimized for performing inferences on convolutional neural networks (CNN). Various design techniques are applied to the log multiplier, including a fully-parallel LOD, efficient shift amount calculation, and exact zero computation. Additionally, the truncation of the operands is studied to create the customizable log multiplier that further reduces energy consumption. The paper also proposes using the one’s complements to handle negative numbers, as an approximation of the two’s complements that had been used in the prior works. The viability of the proposed designs is supported by the detailed formal analysis as well as the experimental results on CNNs. The experiments also provide insights into the effect of approximate multiplication in CNNs, identifying the importance of minimizing the range of error.The proposed customizable design at $w$w = 8 saves up to 88 percent energy compared to the exact fixed-point multiplier at 32 bits with just a performance degradation of 0.2 percent for the ImageNet ILSVRC2012 dataset.

This paper proposes a low-power implementation of the approximate logarithmic multiplier to improve the power consumption of convolutional neural networks for image classification, taking advantage of its intrinsic tolerance to error. The approximate logarithmic multiplier converts multiplications to additions by taking approximate logarithm and achieves significant improvement in power and area while having low worst-case error, which makes it suitable for neural network computation. Our proposed design shows a significant improvement in terms of power and area over the previous work that applied logarithmic multiplication to neural networks, reducing power up to 76.6% compared to exact fixed-point multiplication, while maintaining comparable prediction accuracy in convolutional neural networks for MNIST and CIFAR10 datasets.

TensorFlow [1] is a library developed by Google to implement Artificial Neural Networks using computational dataflow graphs. The neural network has many iterations during training. A distributed, parallel environment is ideal to speedup learning. Parallelism requires proper mapping of devices to TensorFlow operations. We developed HTF-MPR framework for that reason. HTF-MPR utilizes a genetic algorithm approach to search for the best mapping that outperforms the default Tensorflow mapper. By using Gradient Boosting Regressors to create the fitness predictive model, the search space is expanded which increases the chances of finding a solution mapping. Our results on well-known neural network benchmarks, such as ALEXNET, MNIST softmax classifier, and VGG-16, show an overall speedup in the training stage by 1.18, 3.33, and 1.13, respectively.

The divisible load scheduling of image processing applications on the heterogeneous star network is addressed in this paper. In our platform, processors and links have different speeds. Also the computation and communication overheads are considered. A new genetic algorithm for minimizing the processing time of low level image applications using divisible load theory is introduced. A closed form solution for the processing time and the image fractions that should be assigned to each processor are obtained. The optimum number of participating processors and the optimal sequence for load distribution with a new genetic algorithm are derived. The effect of different image and kernel sizes on processing time and speed up are investigated. Finally, to indicate the efficiency of our algorithm, several numerical experiments are presented.

Network-On-Chip (NoC) along with its extension Wireless NoC (WNoC) were proposed to increase system performance in future generations of Multi-Processor System-on-Chip (MPSoC) with hundreds / thousands of cores. For such platforms, designers seek to propose efficient task mapping mechanisms that establish the arrangement of executable tasks taking advantage of available communication links. These proposals are then evaluated and compared against other designs in terms of execution time, latency, energy, communication cost and other metrics, employing simulation tools to that end. However, current WNoC simulators only aim to evaluate the performance of the communication network; they lack the ability to estimate relevant metrics needed for the evaluation of mapping strategies. In this paper, we present an evaluation strategy aimed to assess the performance of task mapping approaches for WNoC and integrate it into a well-known state-of-the-art simulation tool. Several experiments are conducted to demonstrate the benefits of using our proposed strategy.

3D stacking of integrated circuits (ICs) provides significant advantages in saving device footprints, improving power management, and continuing performance enhancement, particularly for many-core systems. However, the stacked structure makes the heat dissipation a challenging issue. While Thermal Through Silicon Via (TTSV) is a promising way of lowering the thermal resistance of dies, past research has either overestimated or underestimated the effects of TTSVs as a consequence of the lack of detailed 3D IC models or system-level simulations. Here, we propose a simulation flow to accurately simulate TTSV effects on 3D ICs. We adopt benchmarks from Splash-2 running on a full-system mode of the gem5 simulator, which generates all the system component activities. McPAT is used to generate the corresponding power consumption and the power traces are fed to HotSpot for thermal simulation. The temperature profiles of 2D and 3D Nehalem-like ×86 processors are compared. TTSVs are later placed close to hotspot regions to facilitate heat dissipation; the peak temperature of 3D Nehalem is reduced by 5--25% with a small area overhead of 6%. By using a detailed 3D thermal model, full-system simulation, and a validated thermal simulator, our results show accurate thermal analysis of 3D ICs.

3D integration opens up new opportunities for future multiprocessor chips by enabling fast and highly scalable 3D Network-on-Chip (NoC) topologies. However, in an aim to reduce the cost of Through-silicon via (TSV), partially vertically connected NoCs, in which only a few vertical TSV links are available, have been gaining relevance. To reliably route packets under such conditions, we introduce a lightweight, efficient and highly resilient adaptive routing algorithm targeting partially vertically connected 3D-NoCs named First-Last. It requires a very low number of virtual channels (VCs) to achieve deadlock-freedom (2 VCs in the East and North directions and 1 VC in all other directions), and guarantees packet delivery as long as one healthy TSV connecting all layers is available anywhere in the network. An improved version of our algorithm, named Enhanced-First-Last is also introduced and shown to dramatically improve performance under low TSV availability while still using less virtual channels than state-of-the-art algorithms. A comprehensive evaluation of the cost and performance of our algorithms is performed to demonstrate their merits with respects to existing solutions.

Biased-Temperature-Instability(BTI) aging mechanism reduces Static-Noise-Margin (SNM) of SRAM cells. This leads to a higher Soft-Error-Rate (SER), lower reliability, and lower SRAMs' stability in FPGAs. SNM partially improves by leveraging the recovery phase of BTI through flipping SRAM content. We propose STABLE, a three-step post-synthesis stress-aware technique, in order to reduce the impact of BTI-induced SNM reduction in FPGA Look-up-Tables (LUTs) using the SAT-based Boolean Matching (BM) algorithm. STABLE partitions Data-Flow-Graph (DFG) of the implemented design into different cones. First, the SAT-based BM algorithm finds a new configuration for each cone while their functionalities are preserved and all SRAMs are flipped. Second, cones that did not pass the first step can benefit from unused SRAMs in their partially-used LUTs for storing the flipped configurations of such LUTs. Finally, flipped configurations of fully-used LUTs are stored in the closest unused LUTs. The main configuration of the implemented FPGA design is swapped by the new flipped configuration, periodically. Our extensive experimental analysis demonstrates 69 and 70 percent on average improvements in the SNM reduction (DSNM) and the SER increase (DSER), respectively. Since the proposed methodology is deployed after the FPGA placement and routing of the application, the overhead is negligible.

2D-NoCs have been the mainstream approach used to interconnect multi-core systems. 3D-NoCs have emerged to compensate for deficiencies of 2D-NoCs such as long latency and power overhead. A low-latency routing algorithm for 3D-NoC is designed to accommodate high-speed communication between cores. Both simulation and analytical models are applied to estimate the communication latency of NoCs. Generally, simulations are time-consuming and slow down the design process. Analytical models provide, within a fraction of the time, nearly accurate results which can be used by simulation to fine-tune the design. In this paper, a high performance and adaptive routing algorithm has been proposed for partially connected 3D-NoCs. Latency of the routing algorithm under different traffic patterns, different number of elevators and different elevator assignment mechanisms are reported. An analytical model, tailored to the adaptivity of the algorithm and under low traffic scenarios, has been developed and the results have been verified by simulation. According to the results, simulation and analytical results are consistent within a 10 percent margin.

In modern many-core architectures, advanced on-chip networks provide the means of communication for the cores. This greatly complicates the design and verification of the cache coherence protocols deployed by those cores. A common approach to deal with this complexity is to decompose the whole system into the protocol and the network. This decomposition is, however, not always possible. For example, unexpected deadlocks can emerge when a deadlock-free protocol and a deadlock-free network are combined. This paper proposes a compositional methodology: prove properties over a network, prove properties over a protocol, and infer properties over the system as a whole. Our methodology is based on theorems that show that such decomposition is possible by having sufficiently large local buffers at the cores. We apply this methodology to verify several protocols such as MI, MSI, MESI and MEUSI running on top of advanced interconnects with adaptive routing.

In this paper, we propose an energy-efficient reconfigurable platform for in-memory processing based on novel four-terminal spin Hall effect-driven domain wall motion devices that could be employed as both nonvolatile memory cell and in-memory logic unit. The proposed designs lead to unity of memory and logic. The device to system level simulation results show that, with 28% area increase in memory structure, the proposed in-memory processing platform achieves a write energy ~15.6 fJ/bit with 79% reduction compared to that of SOT-MRAM counterpart while keeping the identical 1 ns writing speed. In addition, the proposed in-memory logic scheme improves the operating energy by 61.3%, as compared with the recent nonvolatile in-memory logic designs. An extensive reliability analysis is also performed over the proposed circuits. We employ advanced encryption standard (AES) algorithm as a case study to elucidate the efficiency of the proposed platform at application level. Simulation results exhibit that the proposed platform can show up to 75.7% and 30.4% lower energy consumption compared to CMOS-ASIC and recent pipelined domain wall (DW) AES implementations, respectively. In addition, the AES energy-delay product can show 15.1% and 6.1% improvements compared to the DW-AES and CMOS-ASIC implementations, respectively.

To implement a fuzzy system, the first and the most essential step is to design basic fuzzy modules such as analog min and max circuits. This paper presents efficient minimum and maximum circuits using carbon nanotube FETs (CNTFETs) for nanotechnology-based fuzzy circuits and systems. The proposed approach considerably reduces the design complexity in the fuzzy space. In the proposed design, the chirality of carbon nanotubes is utilized for threshold voltage determination. Extensive simulations conducted using HSPICE and the Stanford CNTFET model at 16 nm feature size demonstrate that the proposed fuzzy logic blocks considerably improve the performance parameters and function much more robustly even in the presence of process variations, as compared to their CNTFET-based counterparts.

The movement toward 3D fabrication coupled with Network-on-Chip (NoC) aims to improve area, performance, power, and scalability of many-core systems. However, reliability issue as a perpetual challenge in advanced silicon technology imperils it. Aging is an emerging reliability concern, which degrades the system's performance and causes timing failure eventually. Bias-Temperature-Instability (BTI) and Hot-Carrier-Injection (HCI) are the dominant aging mechanisms, which escalate in high temperature and stress (i.e., usage). In addition to the intra-layer temperature variations, 3D NoCs experience inter-layer temperature variations, which demand necessary investigations for aging as compared to 2D NoC. In this paper, we propose AROMa, an aging-aware deadlock-free adaptive routing algorithm integrated with a novel online aging monitoring system for 3D NoCs. The monitoring system in AROMa exploits Distributed-Centralized-Aging-Table (D-CAT) to obtain routers' aging rates for each layer of 3D NoCs periodically. Consequently, AROMa swaps between different k-best source-destination shortest paths periodically to avoid highly aged routers, force them in recovery phase of BTI, and accordingly balance aging in the network. We prove that AROMa is deadlock free. Our extensive experimental analysis using gem5 full system mode for PARSEC and SPLASH-2 benchmark suites concludes that AROMa outperforms state-of-the-art works while improving age imbalance by 70 percent and maximum age by 35 percent in 3D NoC with negligible overheads.

Scalability of Network-on-Chip (NoC) as a promising solution for many-core systems can be jeopardized due to reliability challenges such as aging in advanced silicon technology. Previous mitigation techniques to protect NoC are either offline, while aging is strictly influenced by runtime operating conditions, or impose significant overheads to the system. This paper presents an online monitoring method through a Centralized Aging Table (CAT) for routers in NoCs. Router's capacity in flits, which are the main stimuli in routers, is predictable and limited for a given period of time. Consequently, stress rate and temperature, which are the major sources of aging mechanisms such as Bias Temperature Instability (BTI) and Hot Carrier Injection (HCI), will be in the predictable ranges, as well. Hence, our methodology uses CAT which is populated by values that represent aging degradation for each different pairs of stress and temperature ranges during a given period of time. Furthermore, utilizing CAT, we propose an online adaptive aging-aware routing algorithm in order to avoid highly aged routers which eventually leads to age balancing between routers. Additionally, our proposed routing algorithm reduces maximum age of routers by changing the shortest paths between source-destination pairs adaptively, considering routers' ages across them in each given period of time. Extensive experimental analysis using gem5 simulator demonstrates that our online routing algorithm and monitoring methodology, CAT, improves delay degradation of maximum aged router and aging imbalance on average by 39% and 52% compared to XY routing, respectively. The impact of our proposed methodology on network latency, Energy-Delay-Product (EDP) and link utilization is negligible.

This paper proposes a highly scalable sensor design for late transition detection in FPGA based platforms. Transition delays occur because of aging mechanisms such as Biased Temperature Instability(BTI) and Hot Carrier Injection (HCI). We propose a sensor clock (SCLK) that is a function of minimum slack time of a set of paths selected for age monitoring. There will be one such clock for many sensors as are needed in an entire FPGA. Our proposed sensor architecture makes it possible for a single SCLK to be shared by all sensors. Additionally, the proposed sensor occupies one slice (basic FPGA logic block), which leads to low area, power, and performance overhead. Using Artix-7-based board, experimental results demonstrate that the proposed aging sensor detects aging earlier than existing sensors and provides less power and performance overheads.

Cache coherence plays a major role in manycore systems. The verification of deadlocks is a challenge in particular, because deadlock freedom is an emerging property. Formal methods often decouple verification of the protocol from verification of the communication interconnect. Modern communication fabrics, however, become more advanced and include a network topology, routing, arbitration, synchronization, and more. In this paper, an integrated approach is proposed that allows cross-layer verification of both the cache coherence protocol and the communication fabric all at once. An automated methodology for deriving cross-layer invariants is proposed. These invariants relate the state of the application-layer protocols to en route packets in the communication fabric. Using the invariants, we derive formal proofs of deadlock-freedom for two case studies: a directory-based MI protocol in a 2D mesh, and a ring-based snoopy protocol in a 2D torus. Additionally, we show that our methodology can be used to derive the smallest possible queue sizes that ensure absence of deadlocks. Our methodology is generally applicable and shows promising scalability.

Fault-tolerant minimal routing algorithms aim at finding a Manhattan path between the source and destination nodes and route around all faulty nodes. Additionally, some non-faulty nodes that are helpless to make up of a fault-tolerant minimal path should also be routed around. How to label such non-faulty nodes efficiently is a major challenge. State-of-the-art solutions could not address it very well. We propose a path-counter method. It can label every node that are helpless to make up of a fault-tolerant minimal path with low time complexity. By counter the number of fault-tolerant minimal paths, it can: support arbitrary fault distribution, check the existence of fault-tolerant minimal paths, not sacrifice any available fault-tolerant minimal paths.

3D ICs can take advantage of a scalable communication platform, commonly referred to as the Networks-on-Chip (NoC). In the basic form of 3D-NoC, all routers are vertically connected. Partially connected 3D-NoC has emerged because of physical limitations of using vertical links. Routing is of great importance in such partially connected architectures. A high-performance, fault-tolerant and adaptive routing strategy with respect to the communication flow among the cores is crucial while freedom from livelock and deadlock has to be guaranteed. In this paper we introduce a new routing algorithm for partially connected 3D-NoCs. The routing algorithm is adaptive and tolerates the faults on vertical links as compared to the predesigned routing algorithms. Our results show a$40-50\%$improvement in the fraction of intact inter-level communications when the fault tolerant algorithm is used. This routing algorithm is light-weight and has only one virtual channel along the$Y$dimension.

As the number of on-chip processor cores increases, power-efficient solutions are sought for data communication between cores. TheHelix-hnon-blocking photonic switch is developed to improve physical-layer and network performance parameters for a wide range of silicon nano-photonic multicore interconnection topologies. Traffic benchmarks and practical case studies using a cycle-accurate simulation environment indicate significantly reduced insertion loss providing improved bandwidth density and scalability to manycore plurality. Improvements in system performance parameters are quantified for network bandwidth, transmission efficiency, and latency in popular photonic internconnection topologies, in comparison to previous switch designs. For instance, utilizing the Helix-h switch in a mesh topology, the bandwidth is increased by 112 percent compared to the previously highest performing switch design. Execution time and energy efficiency are improved by up to 92 and 99 percent, respectively, for representative multicore applications. Finally, the technique is generalized to a novel graph-theoretic method for articulating blocking conditions in photonic switches.

TSV-to-TSV coupling is known to be a significant detriment to signal integrity in three-dimensional (3D) IC architectures. Designing a reliable Through-Silicon Via is critical in order to support better performance. This paper explores the challenges brought on by capacitive and inductive TSV-to-TSV coupling in TSV-based 3D ICs. Based on our analyses, we propose two approaches to mitigate these effects. In one approach, a novel coding technique that adjusts the current flow pattern is proposed to mitigate the inductive coupling effects. In another approach an alternative architecture, wrapping around the TSVs, is proposed to greatly reduce the capacitive coupling effect. The efficiency of the proposed coding methods and supporting architectures is demonstrated by comprehensive simulations at both the hardware and system levels.

Recently, Through-Silicon-Via (TSV) has been more popular to provide faster inter-layer communication in three-dimensional Networks-on-Chip (3D NoCs). However, the area overhead of TSVs reduces wafer utilization and yield which impact design of 3D architectures using a large number of TSVs such as homogeneous 3D NoCs topologies. Also, 3D routers require more memory and thus they are more power hungry than conventional 2D routers. Alternatively, hybrid 3D NoCs combine both the area and performance benefits of 2D and 3D router architectures by using a limited number of TSVs. Existing hybrid architectures suffer from higher packet delays as they do not consider the dynamic communication patterns of different application and their NoC resource usage. We propose a novel algorithm to systematically generate hybrid 3D NoC topologies for a given application such that the vertical connections are minimized while the NoC performance is not sacrificed. The proposed algorithm analyses the target application and generates hybrid architectures by efficiently redistributing the vertical links and buffer spaces based on their utilizations. Furthermore, the algorithm has been evaluated with synthetic and various real-world traffic patterns. Experimental results show that the proposed algorithm generates optimized architectures with lower energy consumption and a significant reduction in packet delay compared to the existing solutions.

TSV-based 3D-NoC has been introduced as a viable solution for integrating more cores on a chip, while imposing smaller footprint area and better timing performance as compared to 2D-NoC. However, TSV-to-TSV coupling is increasingly impacting the reliability of 3D-NoCs due to large size of TSVs. Addressing this issue, various resilient approaches have been recently proposed. But they have been evaluated by uniform random distributions fault modelling, which results in 26%-99% inaccuracy. We propose a system-level TSV-to-TSV coupling fault model that models the capacitive coupling effect, considering thermal impact, with circuit-level accuracy. This model can be plugged into any system-level TSV-based 3D-NoC simulator. It is also capable of identifying faulty TSV bundles and evaluating the efficiency of alternative resilient TSV-based 3D-NoC designs at the system-level.

The cost and reliability issues of TSVs move 3D-NoCs toward heterogonous designs with limited number of TSVs. However, designing a deadlock-free routing algorithm for such heterogonous architectures is extremely challenging due to the increased possibilities of forming cycles between and within layers for 3D designs. In this paper, we target designing a routing algorithm for heterogeneous 3D-NoCs with the capability of working under the technical limit in which there is just one TSV in the network. This algorithm is light-weight and provides adaptivity by using only one virtual channel along the Y dimension.

TSV-to-TSV capacitive coupling has large disruptive effects on timing requirements of the circuit. The latency effect of TSV-to-TSV capacitive coupling for different characteristics of a TSV using circuit-level model is presented in this article. Two coding approaches are proposed to mitigate capacitive parasitic effects by adjusting the current flow pattern for any given n × n mesh of TSV arrangement to reduce the number of 8C/7C parasitic capacitance. The experimental results proves the efficacy of the proposed coding methods.

The network-on-chip (NoC) technology allows for integration of a manycore design on a single chip for higher efficiency and scalability. Three-dimensional (3D) NoCs offer several advantages over two-dimensional (2D) NoCs. Through-silicon via (TSV) technology is one of the candidates for implementation of 3D NoCs. TSV reliability analysis is still challenging for 3D NoC designers because of their unique electrical, thermal, and physical characteristics. After providing an overview of common TSV issues, this article aims to define a reliability criterion for NoC and provide a framework for quantifying this reliability as it relates to TSV issues. TSV issues are modeled as a time-invariant failure probability. Also, a reliability criterion for TSV-based NoC is defined. The relationship between NoC reliability and TSV failure is quantified. For the first time, the reliability criterion is reduced to a tractable closed-form expression that requires a single Monte Carlo simulation. Importantly, the Monte Carlo simulation depends only on network geometry. To demonstrate our proposed method, the reliability criterion of a simple 8×8×8 NoC supported by an 8×8×7 network of TSVs is calculated.

Reliability is one of the most challenging problems in the context of three-dimensional network-on-chip (3D NoC) systems. Reliability analysis is prominent for early stages of the manufacturing process in order to prevent costly redesigns of a target system. This article classifies the potential physical faults of a baseline TSV-based 3D NoC architecture by targeting two-dimensional (2D) NoC components and their inter-die connections. In this paper, through-silicon via (TSV) issues, thermal concerns, and single event effect (SEE) are investigated and categorized, in orderto propose evaluation metrics for inspecting the resiliency of 3D NoC designs. A reliability analysis for major source of faults is reported in this article separately based on their mean time to failure (MTTF). TSV failure probability induced by inductive and capacitive coupling is also discussed. Finally, the paper provides a formal reliability analysis on the aggregated faults that affect TSV. This formal analysis is critical for estimating the resiliency of different components in order to mitigate the redundancy cost of fault-tolerant design or to examine the efficiency of any proposed fault-tolerant methods for 3D NoC architectures.

A 3-D multiple-stacked IC has been proposed to support energy efficiency for data center operations as dynamic RAM (DRAM) scaling improves annually. 3-D multiple-stacked IC is a single package containing multiple dies, stacked together, using through-silicon via (TSV) technology. Despite the advantages of 3-D design, fault occurrence rate increases with feature-size reduction of logic devices, which gets worse for 3-D stacked designs. TSV coupling is one of the main reliability issues for 3-D multiple-stacked IC data TSVs. It has large disruptive effects on signal integrity and transmission delay. In this paper, we first characterize the inductance parasitics in contemporary TSVs, and then we analyze and present a classification for inductive coupling cases. Next, we devise a coding algorithm to mitigate the TSV-to-TSV inductive coupling. The coding method controls the current flow direction in TSVs by adjusting the data bit streams at run time to minimize the inductive coupling effects. After performing formal analyses on the efficiency scalability of devised algorithm, an enhanced approach supporting larger bus sizes is proposed. Our experimental results show that the proposed coding algorithm yields significant improvements, while its hardware-implemented encoder results in tangible latency, power consumption, and area.

Currently, the most powerful supercomputers can provide tens of petaflops. Future many-core systems are estimated to provide an exaflop. However, the power budget limitation makes these machines still unfeasible and unaffordable. Floating Point Units (FPUs) are critical from both the power consumption and performance points of view of today's microprocessors and supercomputers. Literature offers very different designs. Some of them are focused on increasing performance no matter the penalty, and others on decreasing power at the expense of lower performance. In this article, we propose a novel approach for reducing the power of the FPU without degrading the rest of parameters. Concretely, this power reduction is also accompanied by an area reduction and a performance improvement. Hence, an overall energy gain will be produced. According to our experiments, our proposed unit consumes 17.5%, 23% and 16.5% less energy for single, double and quadruple precision, with an additional 15%, 21.5% and 14.5% delay reduction, respectively. Furthermore, area is also diminished by 4%, 4.5 and 5%.

NoC technology is composed of switched-based interconnections, where the communication resources are shared. Therefore, the optimal resource utilization is a crucial consideration for the efficient architecture designs. Application mapping and scheduling are important optimization problems. This paper studies the practicality of the Constraint Programming (CP) models on NoC architecture designs that effectively use a regular mesh with wormhole switching and the XY routing. The complexity of the CP models is compared to the earlier Mixed Integer Programming (MIP) models. Practical CP-based mapping and scheduling models are developed and the results are reported on the benchmark datasets. The results indicate that mapping and scheduling problems can be solved at near optimality even under relatively shorter run-time limits compared to those required by the MIP models.

In this paper, we propose a novel mapping algorithm for providing Quality of Service (QoS) under bandwidth constraints in 3D Network-on-Chip (NoC). The QoS is warranted in such a way that all minimum feasible paths considering the required and available bandwidth are explored by the mapping algorithm. The maximum required bandwidth on the network links for this mapping algorithm is compared with other methods such as NMAP, Onyx and Citrine while applied on two video processing applications i.e. VOPD (Video Object Plane Decoder) and MPEG-4. The available bandwidth of vertical and horizontal links are considered the same and different in the experimental results.

NoC performance largely depends on the underlying deadlock-free and efficient routing algorithm. Selection strategies play a pivotal role in the effectiveness of the routing algorithm by selecting the final output channel when there is more than one possible output link returned by an adaptive routing. In this paper a novel selection strategy, LATEX, is proposed that can be used with any adaptive routing algorithm for specified applications. The objective of the proposed selection strategy is to efficiently balance traffic load and reach better performance results. Performance evaluation is carried out by using a flit-accurate simulator under two real traffic scenarios. Result experiments show that the proposed selection strategy applied to several routing algorithms significantly improves average delay, max delay and power consumption.

Network-on-chip (NoC) architecture is regarded as a solution for future on-chip interconnects. However, the performance advantages of conventional NoC architectures are limited by the long latency and high power consumption due to multi-hop long distance communication among processing elements. To solve these limitations, we employed on-chip wireless communication as express links for transferring data so that transfer latency can be reduced. A hybrid NoC architecture utilizing both wired and wireless communication approaches is proposed in this paper. We also devised a deadlock free routing algorithm that is able to make efficient use of the incorporated wireless links. Moreover, simulated annealing optimization techniques were applied to find optimal locations for wireless routers. Cycle-accurate simulation results showed a significant improvement in transfer latency. Area and power consumption analysis demonstrates the feasibility of our proposed NoC architecture.

This paper proposes a novel QoS-aware and congestion-aware Network-on-Chip architecture that not only enables quality-oriented network transmission and maintains a feasible implementation cost but also well balance traffic load inside the network to enhance overall throughput. By differentiating application traffic into different service classes, bandwidth allocation is managed accordingly to fulfill QoS requirements. Incorporating with congestion control scheme which consists of dynamic arbitration and adaptive routing path selection, high priority traffic is directed to less congested areas and is given preference to available resources. Simulation results show that average latency of high priority and overall traffic is improved dramatically for various traffic patterns. Cost evaluation results also show that the proposed router architecture requires negligible cost overhead but provides better performance for both advanced mesh NoC platforms.

Aggressive scaling of transistors allows integration of hundreds of processors on a chip. However, on-chip interconnects carrying signals between different blocks will be the bottleneck for system performance and reliability. To tackle this problem, we developed an on-chip communication infrastructure based on a network-on-chip architecture and developed a hybrid mechanism to transfer data among IP cores by taking advantages of both wired and wireless communications. By using on-chip antennas, one can provide on-chip wireless communication to transfer data across long distances and minimize transfer latency and energy dissipation accordingly. A wireless network-on-chip architecture was designed and evaluated, and the experimental results showed significant improvement in transfer latency, network throughput and energy dissipation.

As the computation cost increases to meet the design requirements for computation-intensive applications on today's systems, the pressure to develop high performance parallel processors on a chip will increase. Network-on-Chip (NoC) techniques that interconnect multiple processing elements with routers are the solution for reducing computation time and power consumption by parallel processing on a chip. The shared communication platform is also essential to meet the scalability and complexity challenges for System-on-Chip (SoC). However not many parallel applications have been studied for such an architecture and workload characterizations have not been researched to benefit the architecture design optimization. In this paper, we study multiple data-parallel applications on a multicore NoC architecture with distributed memory space. We introduce an efficient runtime workload distribution algorithm that balances workloads of parallel processors and apply for selected embedded applications. Using our cycle accurate multicore simulator, we simulated our NoC-enabled multicore architecture model and executed data-parallel applications on various number of processing elements using the proposed runtime load balancing algorithm and analyzed performance and communication overheads.

This paper proposes a novel Network-on-Chip (NoC) architecture that not only enhances network transmission performance while maintaining implementation cost feasible, but also provides a power-efficient solution for interconnection network scenarios. Diagonally-linked mesh (DMesh) NoC that uses wormhole packet switching technique implements a high-performance NoC platform to meet both cost and power consumption requirements. The proposed architecture uses an adaptive quasi-minimal routing algorithm so that DMesh can improve average latency and saturation traffic load owing to its flexibility and adaptiveness. In addition, implementation results show that employing diagonal links is a more area-efficient way for improving network performance than using large buffers. Simulation results also reveal that power consumption in DMesh networks outperforms traditional Mesh networks.

Low Density Parity Check (LDPC) code is an error correction code that can achieve performance close to Shannon limit and inherently suitable for parallel implementation. It has been widely adopted in various communication standards such as DVB-S2, WiMAX, and Wi-Fi. However, the irregular message exchange pattern is a major challenge in LDPC decoder implementation In addition, faced with an era that diverse applications are integrated in a single system, a flexible, scalable, efficient and cost-effective implementation of LDPC decoder is highly preferable. In this paper, we proposed a multi-processor platform based on network-on-chip (NoC) interconnect as a solution to these problems. By using a distributed and cooperative way for LDPC decoding, the memory bottleneck commonly seen in LDPC decoder design is eliminated. Simulation results from long LDPC codes with various code rates show good scalability and speedups are obtained by our approach.

Ubiquitous and pervasive computing envisions context-aware systems that gather real world information from many fixed and mobile microchips and sensors integrated in everyday objects. To provide valuable services, it is necessary to estimate the location of users or objects. Outdoor location tracking is achieved by Global Positioning System (GPS), but due to its poor indoor coverage, there is a need for alternative technologies in buildings. Since multiple wireless sensors may be situated in the environment, they can be used for location estimation and tracking. This paper presents LocSens, a cost-effective location tracking system based on sensor nodes with wireless connectivity. LocSens works with a minimum number of sensor nodes. It is established and tested in a real indoor scenario over multiple rooms. This paper describes results of several location estimation algorithms and experiences with tracking of moving objects.

RECFEC is a REConfigurable processor optimized for soft implementation of Forward Error Correction (FEC) algorithms. Viterbi, Turbo, Reed-Solomon and LDPC coding algorithms are widely used in wired and wireless standards. The implantation of these algorithms on RECFEC for a multi-mode wireless system is explored and performance metrics are demonstrated. RECFEC is comprised of a pool of processing elements, a processing element controller and memory. Each processing element encapsulates multiple functional units which are optimized for FEC algorithms. Memory includes the configuration and the data buffers. A high bandwidth interconnect network facilitates data movements. Unlike traditional approach to programmable FEC architectures, RECFEC supports multiple algorithms and is instruction-level programmable which results the ultimate flexibility and programmability.

The development cost of low-power embedded systems can be significantly reduced by reusing legacy designs and applying proper modifications to meet the new power constraints. The proposed power management techniques in the literature for implementing distributed power managers in multi-processor systems are very costly in terms of hardware and software modifications. For example, extra software code for power management must be integrated into each component of the system. Furthermore, in order to turn on a component at a specific time/event, extra hardware timers and interrupt controllers must be added to each component along with proper software/device driver modifications. In this paper, we propose a new centralized power management technique that reduces the power consumption of distributed realtime systems at very low implementation cost. Our power manager does not need software and hardware modifications of each individual component. Instead, it uses the model of the system/application to compute the schedule of turning on/off commands by dynamically simulating the system for a given application scenario. The dynamic simulation can be conservative to reflect the jitter in arrival time of events and/or variation in execution delay of tasks. We applied our power management technique to a distributed software-defined radio system and achieved significant energy savings (60% to 87%) at the cost of 1% energy consumed by the power manager itself, as verified by actual hardware measurements. Furthermore, our power manager reacts to the changes in application scenario (referred to as mission) within milliseconds.

Coarse grain reconfigurable arrays (CGRAs) have been drawing attention due to its programmability and performance. Compilation onto CGRAs is still an open problem. Several groups have proposed algorithms that software pipeline loops onto CGRAs. In this paper, we present an efficient modulo scheduling algorithm for a CGRA template. The novelties of the approach are the separation of resource reservation and scheduling, use of a compact three-dimensional architecture graph and a resource usage aware relocation algorithm. Preliminary experiments indicate that the proposed algorithm can find schedules with small initiation intervals within a reasonable amount of time.

OFDM communication systems are widely used in today's wired and wireless system such as ADSL, IEEE 802.11a/g, and DVB-T/H. Current OFDM systems are built on custom ASIC which suffers from a tedious and costly design cycle. In this work we first present an overview of HERS, a heterogeneous reconfigurable system. HERS is a flexible and programmable software defined radio platform and is comprised of a set of heterogeneous reconfigurable engines connected using a high speed bus. Each reconfigurable engine is a specialized reconfigurable processor designed for a class of algorithms and is highly optimized for power and performance. Next, we report on implementation of the most computationally intensive constituent algorithms of IEEE 802.11a/g and DVB-T/H standards.

In this paper, an adaptive wormhole router for a flexible on-chip interconnection network is proposed and implemented for a Chip-mutti processor (CMP). It adopts a wormhole switching technique and its routing algorithm is livelock-/deadlock- free in 2D-mesh topology. Major contribution of this research is the design of an adaptive router architecture adopting a minimal adaptive routing algorithm with near optimal performance and feasible design complexity, satisfying the general SoC design requirements. We also investigate the optimal size of FIFO in an adaptive router with fixed priority scheme.

This paper presents a new technique, called Adaptive Stochastic Gradient Voltage-and-Task Scheduling (ASG-VTS), for power optimization of multicore hard realtime systems. ASG-VTS combines stochastic and energy-gradient techniques to simultaneously solve the slack distribution and task reordering problem. It produces very efficient results with few mode transitions. Our experiments show that ASG-VTS reduces number of mode transitions by 4.8 times compared to traditional energy-gradient-based approaches. Also, our heuristic algorithm can quickly find a solution that is as good as the optimal for a real-life GSM encoder/decoder benchmark. The runtime of ASG-VTS is 150 times and 1034 times faster than energy-gradient based and optimal ILP algorithms, respectively. Since the runtime of ASG-VTS is very low, it is ideal for design space exploration in system-level design tools. We have also developed a web-based interface for ASG-VTS algorithm.

This paper addresses the exploitation of the capabilities of multi-context reconfigurable architectures to handle a variety of interactive multimedia services. One of the main features of these applications is their changing behavior depending on the runtime scenario, turning the configuration management into a key point. In this work, a configuration scheduler for these applications is proposed. We describe the target applications at a task (kernel) granularity by using data flow graphs in which some kernels are conditionally executed depending on runtime conditions. After testing a condition that decides the next kernel to be executed, its corresponding configurations and input data should be loaded into the on-chip memory before its execution starts, producing a computation stall. Our configuration scheduler minimizes these computation stalls and reduces the application's latency by loading configurations before they are needed. Experimental results obtained for interactive and synthetic applications meet their real-time constraints.

Viterbi decoder is used for decoding of convolutional codes in wireless communication protocols. In this paper, implementation of a Viterbi decoder on a dynamically reconfigurable architecture is presented. Performance of this implementation for applications like W-CDMA, WLAN and WiMAX is studied.

Programmable solutions for fast mobile communication systems are attracting ever-growing attention due to different and also evolving communication standards. They overcome the shortcomings of ASIC design, by allowing multimode operation, and general-purpose processors by exploiting the inherent data level parallelism in the application. MaRS, a macro-pipelined reconfigurable system, is a domain specific programmable parallel DSP architecture, aimed at harnessing the inherent parallelism in such applications. In this paper, we present the MaRS architecture along with the latest modifications and algorithms that are mapped onto it. We have mapped an IEEE 802.11a WLAN transmitter including a parallel FFT and soft decision Viterbi decoder on MaRS. Our simulation results show that the performance achieved on MaRS meets the stringent timing constraints of the IEEE 802.11a baseband transceiver at its highest rate, with 20% slack, leaving a playground for system level power optimization. Finally, we have mapped the EEMBC telecom suite on MaRS to evaluate and compare our architecture with existing architectures.

Reconfigurable architectures have becoming very relevant in recent years. In this paper we propose a methodology dedicated to analyze interactive applications in order to execute them in a SIMD reconfigurable architecture taking into account power/performance trade-offs. This methodology starts from a kernel description of the interactive application. Kernels are conditionally executed depending on dynamic conditions like user's input data manipulation. The volume of data involved in this kind of applications combined with user's actions occurring at unexpected times strongly impact on performance. We define an execution model to deal with conditional branches accompanied by a data prefetch scheme in order to avoid reconfigurable processing unit stalls due to operands unavailability. Experimental results satisfy time constraints of interactive applications and show a power effective solution for them.

Increasing demand for larger high-performance applications requires developing more complex systems with hundreds of processing cores on a single chip. To allow dynamic voltage scaling in each on-chip cores individually, many on-chip voltage regulators must be used. However, the limitations in implementation of on-chip inductors can reduce the efficiency, accuracy and the number of voltage modes generated by regulators. Therefore the future voltage scheduling algorithms must be efficient, even in the presence of few voltage modes; and fast, in order to handle complex applications. Techniques proposed to date, need many fine-grained voltage modes to produce energy efficient results and their quality degrades significantly as the number of modes decreases. This paper presents a new technique called Adaptive Stochastic Gradient Voltage and Task Scheduling (ASG-VTS) that quickly generates very energy efficient results irrespective of the number of available voltage modes. The results of comparing our algorithm to the most efficient approaches (RVS and EE-GLSA) show that in the presence of only four valid modes, the ASG-VTS saves up to 26% and 33% more energy. On the other hand, other approaches require at least ten modes to reach the same level of energy saving that ASG-VTS achieves with only four modes. Therefore our algorithm can also be used to explore and minimize the number of required voltage levels in the system.

MorphoSys is a reconfigurable SIMD architecture. In this paper, a BSP-based ray tracing is gracefully mapped onto MorphoSys. The mapping highly exploits ray-tracing parallelism. A straightforward mechanism is used to handle irregularity among parallel rays in BSP. To support this mechanism, a special data structure is established, in which no intermediate data has to be saved. Moreover, optimizations such as object reordering and merging are facilitated. Data starvation is avoided by overlapping data transfer with intensive computation so that applications with different complexity can be managed efficiently. Since MorphoSys is small in size and power efficient, we demonstrate that MorphoSys is an economic platform for 3D animation applications on portable devices.

The trend towards distributed, networked embedded systems is changing the way power should be managed. Power consumed by bus and network interfaces now matches if not surpasses that of the CPU and is thus becoming a prime candidate for reduction. This paper explores energy-efficient bus topologies as a new technique for global power optimization of embedded systems that are interconnected by high-speed serial network-like busses such as FireWire and a new generation of SoC buses. Our grammar-based representation for these networks enables selection of energy-efficient bus topologies. Experimental results show 15-20% energy saving on the network interfaces without sacrificing system performance.

The Adaptive Computing Systems (ACS) program was initiated by Defense Advanced Research Projects Agency (DARPA) of the United States in 1996. With the advent of FPGAs, has emerged a new class of computing systems that contain configurable hardware. This session begins by a presentation by the first ACS program manager of its motivation, original goals, and objectives. It is then followed by presentations of four specific projects under the ACS program. Future activities surrounding the ACS community will be discussed at the end.

MorphoSys is a reconfigurable SIMD architecture. In this paper, a BSP-based ray tracing is gracefully mapped onto MorphoSys. The mapping highly exploits ray-tracing parallelism. A straightforward mechanism is used to handle irregularity among parallel rays in BSP. To support this mechanism, a special data structure is established, in which no intermediate data has to be saved. Moreover, optimizations such as object reordering and merging are facilitated. Data starvation is avoided by overlapping data transfer with intensive computation so that applications with different complexity can be managed efficiently. Since MorphoSys is small in size and power efficient, we demonstrate that MorphoSys is an economic platform for 3D animation applications on portable devices.

Camera calibration is a critical problem in applications such as augmented reality and image based model reconstruction. When constructing a 3D model of an object from an uncalibrated video sequence, large amounts of frames and self occlusions of parts of the object are common and difficult problems. In this paper we present a fast and robust algorithm that uses a divide and conquer strategy to split the video sequence into sub-sequences containing only the most relevant frames. Then a robust stratified linear based algorithm is able to calibrate each of the subsequences to a metric structure and finally the subsequences are merged together and a final nonlinear optimization refines the solution. Examples of real data reconstructions are presented.

We present implementation of a very fast parallel complex FFT on M2, the second generation of MorphoSys reconfigurable computation platform, which is targeting on streamed applications such as multimedia and DSP. The proposed mapping comprises fast presorting, cascaded radix-2 stages, and postreordering. Data and twiddle factors are 16-bit real and 16-bit imaginary in 2's complement format and scaling is performed to avoid overflow. The mapping is tested on our cycle-accurate simulator, "mulate", and the performance is encouragingly better than other architectures such as Imagine and VIRAM. Moreover, the performance is scalable according to FFT sizes. Since there is no functionality specifically tailored to FFT, the results demonstrate the capability of MorphoSys architecture to extract parallelism from streamed applications. Further rationales are given based on the concepts of scalar operand networks and memory hierarchy.

The rapid growth of device densities on silicon has made it feasible to deploy reconfigurable hardware as a highly parallel computing platform. However, one of the obstacles to the wider acceptance of this technology is its programmability. The application needs to be programmed in hardware description languages or an assembly equivalent, whereas most application programmers are used to the algorithmic programming paradigm. SA-C has been proposed as an expression-oriented language designed to implicitly express data parallel operations. The Morphosys project proposes an SoC architecture consisting of reconfigurable hardware that supports a data-parallel, SIMD computational model. This paper describes a compiler framework to analyze SA-C programs, perform optimizations, and automatically map the application onto the Morphosys architecture. The mapping process is static and it involves operation scheduling, processor allocation and binding, and register allocation in the context of the Morphosys architecture. The compiler also handles issues concerning data streaming and caching in order to minimize data transfer overhead. We have compiled some important image-processing kernels, and the generated schedules reflect an average speedup in execution times of up to 6× compared to the execution on 800 MHz Pentium III machines.

A new technique is presented in this paper to improve the efficiency of data scheduling for multi-context reconfigurable architectures targeting multimedia and DSP applications. The main goal is to improve the applications execution time minimizing external memory transfers. Some amount of on-chip data storage is assumed to be available in the reconfigurable architecture. Therefore the Complete Data Scheduler tries to optimally exploit this storage, saving data and result transfers between on-chip and external memories. In order to do this, specific algorithms for data placement and replacement have been designed. We also show that a suitable data scheduling could decrease the number of transfers required to implement the dynamic reconfiguration of the system.

This paper presents a novel method for improving the operation autonomy of the processing elements (PE) of SIMD-like machines. By combining guarded instructions and pseudo branches it is possible to achieve higher operation autonomy and higher instruction level parallelism than in previous SIMD/ASIMD architectures. The paper shows that it is feasible to avoid most branches and it is also possible to emulate conditional execution on the processing elements, either by using guarded instructions or by using pseudo branches, thus avoiding unnecessary intervention by the array control unit in data-dependant computations. Pseudo branches are used when it is not possible to use guarded instructions. Additionally, they also support the implementation of complex nested if-then-else constructs, improving the execution of irregular dataparallel applications. The paper also shows that the simplicity of the method allows it to be implemented both in fine-grain and coarse-grain SIMD/ASIMD architectures because it does not require significant additional silicon area. Finally, it is shown that pseudo branches can be used to control the power saving of those processing elements that have instructions nullified.

This paper presents an architecture for running interactive ray tracing applications on portable devices such as cell phones, PDAs, and head mounted displays and discusses the main issues related to the mapping of this graphics algorithm using fixed-point arithmetic. The paper shows that a floating-point arithmetic unit, with its associated power and area consumption, can be avoided by using appropriate fixed-point arithmetic and block floating-point operations. It is also shown that a computation intensive graphics method like ray tracing can be used to generate simple images at interactive rates on portable devices. This can be achieved by employing a reconfigurable SIMD architecture on a chip, which trades parallelism for frequency of operation, thus providing significant benefits in power saving, which is essential in portable devices.

The rapid growth of silicon densities has made it feasible to deploy reconfigurable hardware as a highly parallel computing platform. However, in most cases, the application needs to be programmed in hardware description or assembly languages, whereas most application programmers are familiar with the algorithmic programming paradigm. SA-C has been proposed as an expression-oriented language designed to implicitly express data parallel operations. Morphosys is a reconfigurable system-on-chip architecture that supports a data-parallel, SIMD computational model. This paper describes a compiler framework to analyze SA-C programs, perform optimizations, and map the application onto the Morphosys architecture. The mapping process involves operation scheduling, resource allocation and binding and register allocation in the context of the Morphosys architecture. The execution times of some compiled image-processing kernels can achieve up to 42x speed-up over an 800 MHz Pentium III machine.

Power-aware systems are those that must make the best use of available power. They subsume traditional low-power systems in that they must not only minimize power when the budget is low, but also deliver high performance when required. This paper presents a new scheduling technique for supporting the design and evaluation of a class of power-aware systems in mission-critical applications. It satisfies stringent min/max timing and max power constraints. It also makes the best effort to satisfy the min power constraint in an attempt to fully utilize free power or to control power jitter. Experimental results show that our scheduler can improve performance and reduce energy cost simultaneously compared to hand-crafted designs for previous missions. This tool forms the basis of the IM-PACCT system-level framework that will enable designers to explore many power-performance trade-offs with confidence. 1.

We develop a new software layer called the Automatic Parallel Detection Layer (APDL) for the automatic transformation from sequential to parallel code. The main interest, in this research, is the parallelism at loop level, because significant parallelism in programs almost invariably occurs in loops. The proposed APDL has five processes for code transformation: the sequential source code parser, data dependence analysis of this code, partitioning, scheduling both task and data, and generating parallel source code. Many cases have been studied to evaluate the performance of the developed layer. The performance is evaluated depending on the execution time of: the sequential code, the parallel programmer code, and the code output from APDL for the same case study. Performance results show that APDL greatly improves the execution time with respect to sequential execution time, and saves on the high cost of a parallel programmer.

In this paper, we analyze the main issues in context scheduling for multicontext reconfigurable architectures from a formal point of view. We first provide an intuitive approach. which is later supported by a detailed analysis of the mathematical relations that express the reconfiguration process. This enables us to deduce a methodology for the minimization of context loading overhead, which considers the tradeoff between achievable system performance and algorithm efficiency. In this respect, the optimality necessary conditions are established in order to contrive an optimal search. However, as this approach is very time consuming we propose some heuristic techniques that reduce the algorithm complexity and accomplish very good results in relatively short execution time. This work has been developed as a part of an automated design environment for reconfigurable systems. A set of experiments has been developed so as to validate the theoretical results.

Dynamically reconfigurable architectures are emerging as a viable design alternative to implement a wide range of computationally intensive applications. At the same time, an urgent necessity has arisen for support tool development to automate the design process and achieve optimal exploitation of the architectural features of the system. Task scheduling and context (configuration) management become very critical issues in achieving the high performance that digital signal processing (DSP) and multimedia applications demand. This article proposes a strategy to automate the design process which considers all possible optimizations that can be carried out at compilation time, regarding context and data transfers. This strategy is general in nature and could be applied to different reconfigurable systems. We also discuss the key aspects of the scheduling problem in a reconfigurable architecture such as MorphoSys. In particular, we focus on a task scheduling methodology for DSP and multimedia applications, as well as the context management and scheduling optimizations.

In this paper, we present a case study for the design, programming and usage of a reconfigurable system-on-chip, MorphoSys, which is targeted at computation-intensive applications. This 2-million transistor design combines a reconfigurable array of cells with a RISC processor core and a high bandwidth memory interface. The system architecture, software tools including a scheduler for reconfigurable systems, and performance analysis (with impressive speedups) for target applications are described.

This paper describes a methodology to efficiently obtain a solution to the problem of context scheduling for multi-context reconfigurable architectures, regarding the minimization of context loading overhead. The target applications are assumed to be periodic, since it is a typical feature of many DSP and multimedia applications. This paper considers the trade-off between achievable system performance and algorithm efficiency. It has been developed as a part of an automated design environment for reconfigurable systems.

This paper describes a methodology to efficiently obtain a solution to the problem of context scheduling for multi-context reconfigurable architectures, regarding the minimization of context loading overhead. The target applications are assumed to be periodic, since it is a typical feature of many DSP and multimedia applications. This work considers the trade-off between achievable system performance and algorithm efficiency. It has been developed as a part of an automated design environment for reconfigurable systems.

This paper introduces MorphoSys, a reconfigurable computing system developed to investigate the effectiveness of combining reconfigurable hardware with general-purpose processors for word-level, computation-intensive applications. MorphoSys is a coarse-grain, integrated, and reconfigurable system-on-chip, targeted at high-throughput and data-parallel applications. It is comprised of a reconfigurable array of processing cells, a modified RISC processor core, and an efficient memory interface unit. This paper describes the MorphoSys architecture, including the reconfigurable processor array, the control processor, and data and configuration memories. The suitability of MorphoSys for the target application domain is then illustrated with examples such as video compression, data encryption and target recognition. Performance evaluation of these applications indicates improvements of up to an order of magnitude (or more) on MorphoSys, in comparison with other systems.

Reconfigurable computing is a flexible way of facing with a single device a wide range of applications with a good level of performance. This area of computing involves different issues and concepts when compared with conventional computing systems. One of these concepts is context lending. The context refers to the coded configuration information to implement a particular circuit behaviour. An important problem for reconfigurable computing is the scheduling of a group of kernels (sub-tasks) that constitute a complex application for minimum execution time. In this paper, we show how the different execution orders for these sub-tasks may result in varying levels of performance. We formulate an analytical approach and present a solution for this new problem through this work.

We discuss the problem of packing hypercubes into an n-dimensional star graph S(n), which consists of embedding a disjoint union of hypercubes U into S(n) with load one. Hypercubes in U have from [n/2] to (n+1)/spl middot/[log/sub 2/ n]-2([lod/sub 2/n]+1)+2 dimensions, i.e., they can be as large as any hypercube which can be embedded with dilation at most four into S(n). We show that U can be embedded into S(n) with optimal expansion, which contrasts with the growing expansion ratios of previously known techniques. We employ several performance metrics to show that, with our techniques, a star graph can efficiently execute heterogeneous workloads containing hypercube, mesh, and star graph algorithms. The characterization of our packings includes some important metrics which have not been addressed by previous research (namely, average dilation, average congestion, and congestion). Our packings consistently produce small average congestion and average dilation, which indicates that the induced communication slowdown is also small. We consider several combinations of node mapping functions and routing algorithms in S(n), and obtain their corresponding performance metrics using either mathematical analysis or computer simulation.

Instruction fetching is critical to the performance of a superscalar microprocessor. We develop a mathematical model for three different cache techniques and evaluate its performance both in theory and in simulation using the SPEC95 suite of benchmarks. In all the techniques, the fetching performance is dramatically lower than ideal expectations. To help remedy the situation, we also evaluate its performance using prefetching. Nevertheless, fetching performance is fundamentally limited by control transfers. To solve this problem, we introduce a new fetching mechanism called a dual branch target buffer. The dual branch target buffer enables fetching performance to leap beyond the limitation imposed by conventional methods and achieve a high instruction fetching rate.

Accurate branch prediction and instruction fetch prediction of a microprocessor are critical to achieve high performance. For a processor which fetches and executes multiple instructions per cycle, an accurate and high bandwidth instruction fetching mechanism becomes increasingly important to performance. Unfortunately, the relatively small basic block size exhibited in many general-purpose applications severely limits instruction fetching. In order to achieve a high fetching rate for wide-issue superscalars, a scalable method to predict multiple branches per block of sequential instructions is presented. Its accuracy is equivalent to a scalar two-level adaptive prediction. Also, to overcome the limitation imposed by control transfers, a scalable method to predict multiple blocks is presented. As a result, a two black, multiple branch prediction mechanism for a block width of 8 instructions achieves an effective fetching rate of 8 instructions per cycle on the SPEC95 benchmark suite.

This paper describes a technique for improving the performance of a superscalar processor through multithreading. The technique exploits the instruction-level parallelism available both inside each individual stream, and across streams. The former is exploited through out-of-order execution of instructions within a stream, and the latter through execution of instructions from different streams simultaneously. Aspects of multithreaded superscalar design, such as fetch policy, cache performance, instruction scheduling, and functional unit utilization are studied. We analyze performance based on the simulation of a superscalar architecture and show that it is possible to provide support for multiple streams with minimal extra hardware, yet achieving significant performance gain (20-55%) across a range of benchmarks.

Binary tree structures have been very useful in solving divide-and-conquer type of problems. Embedding binary trees into another network-the host network-helps in designing solutions for the host network using the known solutions on binary trees. Embedding arbitrary binary trees into networks, in particular into the hypercube, has been addressed in the literature. The latter was achieved with load 1 and constant dilation. The n-star graph is a recently introduced interconnection network for massively parallel systems. It enjoys symmetry and fault tolerance properties that make it a viable alternative to the hypercube. In this paper, we address the problem of embedding arbitrary binary trees into the n-star graph. This work is the first to present such an embedding. The tree has [e(n-1)1] or fewer vertices. The embedding leads to load 1 and constant dilation for all values of n. It therefore enables the star graph to efficiently simulate an arbitrary binary tree with only a constant factor of communication delay.

The maxim of the superscalar architecture is that higher performance can be achieved by executing multiple instructions simultaneously. This can be realized on hardware by using a centralized instruction window. We present the design and implementation of a centralized instruction window capable of out-of-order issue and completion of four instructions per cycle. A compact layout (6.4 mm by 2.2 mm) of a 32-entry instruction window resulted from a full-custom design in 1.0 /spl mu/m (drawn) 3-layer metal CMOS technology. The layout was verified by simulation and shown to operate at a clock frequency over 100 MHz.

An enumeration of star graphs is given which has many useful properties. For example an arbitrary prefix or suffix is connected; indeed the diameter is O(n). As a consequence, there is an O(n) interval broadcast algorithm. Prefixes which have t(n-1)! vertices for some t are especially well-behaved. The topology of, embeddings in, and algorithms for these graphs are considered, making use of the enumeration.>

Cache, dynamic scheduling, bypassing, branch prediction, and fetch efficiency are primary issues concerning performance of a superscalar microprocessor. This paper considers all these issues and shows their impact on performance by running our simulator on seventeen different programs. Our approach in handling branch prediction is shown to significantly decrease the bad branch penalty. Furthermore, results show that the average instruction fetch places an upper bound on speedup and is the most critical factor in determining overall performance. Its performance impact is greater than all other factors combined.

This paper considers the problem of detecting lines in images using a pyramid architecture. The approach is based on the Hough Transform calculation. A pyramid architecture of size n is a fine-grain architecture with a mesh base of size [Formula: see text] processors each holding a single pixel of the image. The pyramid operates in an SIMD mode. Two algorithms for computing the Hough Transform are explained. The first algorithm initially uses different angles, θj’s, and its complexity is O(k+log n) with O(m) storage requirement. The second algorithm computes the Hough Transform in a pipeline fashion for each angle θj at a time. This method produces results in O(k * log n) time with O(1) storage, where k is the number of θj angles, m is the number of ρi normal distances from the origin, and n is the number of pixels. A simulation program is also described.

This short note describes issues involved in the bypassing mechanism for a very long instruction word (VLIW) processor and its relation to the pipeline structure of the processor. The authors first describe the pipeline structure of their processor and analyze its performance and compare it to typical RISC-style pipeline structures given the context of a processor with multiple functional units. Next they study the performance effects of various bypassing schemes in terms of their effectiveness in resolving pipeline data hazards and their effect on the processor cycle time.>

Introduces a new interconnection network for massively parallel systems called the incomplete star graph. The authors describe unique ways of interconnecting and labeling the nodes and routing point-to-point communications within this network. In addition, they provide an analysis of a special class of incomplete star graph called C/sup n/spl minus/1/ graph and obtain the diameter and average distance for this network. For the C/sup n/spl minus/1/ graph, an efficient broadcasting scheme is presented. Furthermore, it is proven that a C/sup n/spl minus/1/ with N nodes (i.e. N=m(n/spl minus/1)!) is Hamiltonian if m=4 or m=3k, and k/spl ne/2.>

This paper introduces a new interconnec tion network for massively parallel systems referred to as star connected cycles (SCC) graph. The SCC presents a fixed degree structure that results in several advantages over variable degree graphs like the star graph and the n-cube. The description of the SCC graph given in this paper in cludes issues such as labeling of nodes, degree, diameter, symmetry, fault tolerance and Cayley graph representation. The paper also presents an optimal routing algorithm for the SCC and a comparison with other interconnection net works. Our results indicate that for even n, an n-SCC and a CCC of similar sizes have about the same diameter.

The authors present a routing algorithm that uses the depth first search approach combined with a backtracking technique to route messages on the star graph in the presence of faulty links. The algorithm is distributed and requires no global knowledge of faults. The only knowledge required at a node is the state of its incident links. The routed message carries information about the followed path and the visited nodes. The algorithm routes messages along the optimal, i.e., the shortest path if no faults are encountered or if the faults are such that an optimal path still exists. In the absence of an optimal path, the algorithm always finds a path between two nodes within a bounded number of hops if the two nodes are connected. Otherwise, it returns the message to the originating node. The authors provide a performance analysis for the case where an optimal path does not exist. They prove that for a maximum of n-2 faults on a graph with N=n! nodes, at most 2i+2 steps are added to the path, where i is O( square root n). Finally, they use the routing algorithm to present an efficient broadcast algorithm on the star graph in the presence of faults.>

A systematic approach for mapping application tasks to hypercubes is proposed. This method is based on a partitioning algorithm in which the final mapping is rendered as a task-node tuple assignment for an n-cube system. For this method, a single-tasking environment in which each task is assigned to a unique processor is assumed. Dilation-bound and expansion-ratio parameters are used to evaluate the efficacy of this mapping algorithm. An algorithm that minimizes the expansion-ratio parameter is introduced. In addition, an algorithm that reduces the dilaton bound is proposed. Because of the structured formation of the algorithms, they can be applied to any given task structure. As an illustration of the effectiveness of this method, the proposed algorithms are applied to mapping complete binary and d-ary tree task structures to hypercubes.>

This paper describes issues involved in the bypassing mechanism for a VLIW processor and its relation to the pipeline structure of the processor. We will first describe the pipeline structure of our processor and analyze its performance and compare it to typical RISC-style pipeline structures given the context of a processor with multiple functional units. Next, we shall study the performance effects of various bypassing schemes in terms of their effectiveness in resolving pipeline data hazards and their effect on the processor cycle time.

The problem of distributed garbage collection is discussed. An algorithm for parallel distributed asynchronous garbage collection is presented. The liveness and safety properties of this method are demonstrated. The algorithm does not require a global clock, complex termination detection methods, or distributed synchronization techniques. A new color code is introduced to distinguish between local cells (black) and those that are exclusively accessible from the remote pointers (gray). The mutator operation is revised to handle a multiple mutator scheme on a given local memory. Simulation results show that the developed distributed and parallel algorithm performs much better than the sequential method as tested on a Balance 8000 computer.>