Network-on-Chip (NoC) congestion builds up during heavy traffic load and leads to wasted link bandwidth, crippling the system performance. We propose a lightweight machine learning-based technique that helps predict congestion in the net-work by collecting features related to traffic at each destination and labelling it using a novel time reversal approach. The labelled data is used to design a low overhead and an explainable decision tree model used at runtime congestion control. Experimental evaluations with synthetic and real traffic on industrial$\boldsymbol{6\times 6}$NoC show that the proposed approach increases fairness and memory read bandwidth by up to 114% with respect to existing congestion control technique while incurring less than 0.01% of overhead.

Large-scale manycore System-on-Chips (SoCs) need to satisfy the conflicting objectives of maximizing performance and minimizing energy consumption for dynamically changing applications. In this paper, we consider the problem of dynamic power management (DPM) in large manycore SoCs for unseen applications at runtime. We employ a machine learning (ML) based DPM policy, which selects the voltage/frequency (V/F) levels for different cluster of cores as a function of the application features such as core computation, inter-core traffic etc. We propose a novel uncertainty-aware online learning framework to learn the DPM policy, which can adapt to unseen applications at runtime. It relies on two key ideas. First, an entropy-based uncertainty measure is used to distinguish between seen and unseen system states. Second, we employ conformal prediction to compute uncertain V/F sets for unseen system states. We perform bounded-search over the uncertain V/F configurations using power/performance models to identify the best V/F configurations to minimize the energy-delay product (EDP) and create supervised examples for online learning. Our experiments on 64-core system show that the EDP is reduced by up to 50 % and 60 % when compared to existing online-imitation learning and reinforcement learning methods, respectively.

Process technology-driven performance and energy efficiency improvements have slowed down as we approach physical design limits. General-purpose manycore architectures attempt to circumvent this challenge, but they have a significant performance and energy-efficient gap compared to special-purpose solutions. Domain-specific architectures (DSAs), an instance of heterogeneous architectures, efficiently combine general-purpose cores and specialized hardware accelerators to boost energy efficiency and provide programming flexibility. Indeed, the hardware, software, and systems aspects in DSAs are highly tailored to maximize the energy efficiency of applications in a target domain. As DSAs and their conceptualization advance rapidly, there is a strong need to understand the research problems that need immediate attention. This article discusses the primary research directions in the design and runtime management of DSAs. Then, it surveys some promising approaches and highlights the outstanding research needs.

Domain-specific systems-on-chip (DSSoCs), a class of heterogeneous many-core systems, are recognized as a promising approach to narrowing down the performance and energy-efficiency gap between custom hardware accelerators and programmable processors.However, fulfilling this promise depends on successfully addressing a number of fundamental research questions.For instance, given a target domain, a designer must develop a suitable architecture and determine the set of appropriate hardware accelerators.While integrating too many accelerators would increase the design cost, missing critical accelerators can undermine the system performance and energy efficiency.Typically, a rich set of accelerators can dramatically lower the processing times.Hence, the rest of the system components, such as the on-chip communication, must also match the high performance requirements and enable nanosecond-level latencies between the IP blocks and accelerators.DSSoCs must also provide software tools, application programming interfaces (APIs), and accelerator interfaces such that application developers can utilize them efficiently.Finally, a range of runtime management methodologies and algorithms are required to make the best use of the DSSoC resources and power budgets.This Special Issue presents eleven research papers and a survey targeting these topics selected from over 40 submissions.It represents a remarkable collective effort involving both the academic and industrial research communities.The articles in this issue present novel and impactful solutions to important research problems, including novel device technologies, hardware accelerators, high-level synthesis techniques, design space exploration, scheduling, virtualization, compiler, and test techniques for domain-specific designs.The survey article titled "Domain-Specific Architectures (DSAs): Research Problems and Promising Approaches" provides a comprehensive overview of various research directions, outstanding challenges, and promising approaches in DSSoC system design.Starting from the lowest level of abstraction, the article "Experimental Demonstration of STT-MRAM-based Nonvolatile Instantly On/Off System: Case Studies" presents a solution for IoT applications using nonvolatile STT-MRAMs.Experimental results show 15.1% lower power consumption with two orders of magnitude faster data restore time.At the hardware design level, the paper titled "SHARP: An Adaptable, Energy-Efficient Accelerator for Recurrent Neural Network" identifies adaptiveness as a key feature missing from existing RNN accelerators.It proposes an intelligent tiled-based dispatching mechanism to efficiently handle the data dependencies.The

The complexity of manycore System-on-chips (SoCs) is growing faster than our ability to manage them to reduce the overall energy consumption. Further, as SoC design moves toward three-dimensional (3D) architectures, the core's power density increases leading to unacceptable high peak chip temperatures. In this article, we consider the optimization problem of dynamic power management (DPM) in manycore SoCs for an allowable performance penalty (say, 5%) and admissible peak chip temperature. We employ a machine learning– (ML) based DPM policy, which selects the voltage/frequency levels for different cluster of cores as a function of the application workload features such as core computation and inter-core traffic, and so on. We propose a novel learning-to-search (L2S) framework to automatically identify an optimized sequence of DPM decisions from a large combinatorial space for joint energy-thermal optimization for one or more given applications. The optimized DPM decisions are given to a supervised learning algorithm to train a DPM policy, which mimics the corresponding decision-making behavior. Our experiments on two different manycore architectures designed using wireless interconnect and monolithic 3D demonstrate that principles behind the L2S framework are applicable for more than one configuration. Moreover, L2S-based DPM policies achieve up to 30% energy-delay product savings and reduce the peak chip temperature by up to 17 °C compared to the state-of-the-art ML methods for an allowable performance overhead of only 5%.

Weighted round-robin (WRR) arbitration provides global fairness in networks-on-chip (NoCs) as opposed to the commonly used round-robin and priority-based arbitration techniques. However, the large number of weights explodes the design space and exacerbates performance (latency-throughput) tuning. Therefore, fast and accurate performance analysis techniques for NoCs are crucial for accelerating design space exploration and accurate pre-silicon evaluation. This article presents the first comprehensive performance analysis technique for NoCs with WRR arbitration and finite buffers. It can handle bursty traffic and is scalable to large NoC sizes. The proposed technique first estimates the probability that a queue is full and uses this result to compute the modified service time and queuing delay. Thorough experimental evaluations with synthetic traffic and real applications show that the proposed analytical model is always more than 10% accurate compared to cycle-accurate simulations. Moreover, the proposed performance analysis technique is five orders of magnitude faster than cycle-accurate simulations for a$16\times16$mesh NoC.

Network Function Virtualization (NFV), the replacement of purpose-built network appliances with software functions running on general purpose compute servers, is ubiquitous in today's telecommunication networks. The 5G User Plane Function (UPF) is an important example of an NFV workload, which enables 5G and internet communications. The UPF has strict packet drop requirements and because user traffic load can vary dramatically throughout the day, the selection of a single static configuration leads to over-provisioning of server resources. To reduce the cost of ownership, network operators can reduce power consumption during periods of low traffic load, but to do so they must ensure that packet drop requirements are met. In this paper we present DPM-NFV, a machine learning based framework that enables dynamic tuning of a real NFV system. Our methodology is composed of two phases: (1) Offline, targeted automated studies use Bayesian Optimization to infer the best configurations for various load levels; (2) Online, a run-time classifier dynamically selects the best configuration for the current load. Our results obtained on a real system demonstrate that the UPF can meet strict packet drop requirements while reducing power consumption by up to 52% with smooth traffic and up to 46% with bursty traffic.

Processor design validation and debug is a difficult and complex task, which consumes the lion's share of the design process. Design bugs that affect processor performance rather than its functionality are especially difficult to catch, particularly in new microarchitectures. This is because, unlike functional bugs, the correct processor performance of new microarchitectures on complex, long-running benchmarks is typically not deterministically known. Thus, when performance benchmarking new microarchitectures, performance teams may assume that the design is correct when the performance of the new microarchitecture exceeds that of the previous generation, despite significant performance regressions existing in the design. In this work we present a two-stage, machine learning-based methodology that is able to detect the existence of performance bugs in microprocessors. Our results show that our best technique detects 91.5% of microprocessor core performance bugs whose average IPC impact across the studied applications is greater than 1% versus a bug-free design with zero false positives. When evaluated on memory system bugs, our technique achieves 100% detection with zero false positives. Moreover, the detection is automatic, requiring very little performance engineer time.

Fast and accurate performance analysis techniques are essential in early design space exploration and pre-silicon evaluations, including software eco-system development. In particular, on-chip communication continues to play an increasingly important role as the many-core processors scale up. This paper presents the first performance analysis technique that targets networks-on-chip (NoCs) that employ weighted round-robin (WRR) arbitration. Besides fairness, WRR arbitration provides flexibility in allocating bandwidth proportionally to the importance of the traffic classes, unlike basic round-robin and priority-based arbitration. The proposed approach first estimates the effective service time of the packets in the queue due to WRR arbitration. Then, it uses the effective service time to compute the average waiting time of the packets. Next, we incorporate a decomposition technique to extend the analytical model to handle NoC of any size. The proposed approach achieves less than 5% error while executing real applications and 10% error under challenging synthetic traffic with different burstiness levels.

Dynamic resource management has become one of the major areas of research in modern computer and communication system design due to lower power consumption and higher performance demands. The number of integrated cores, level of heterogeneity and amount of control knobs increase steadily. As a result, the system complexity is increasing faster than our ability to optimize and dynamically manage the resources. Moreover, offline approaches are sub-optimal due to workload variations and large volume of new applications unknown at design time. This paper first reviews recent online learning techniques for predicting system performance, power, and temperature. Then, we describe the use of predictive models for online control using two modern approaches: imitation learning (IL) and an explicit nonlinear model predictive control (NMPC). Evaluations on a commercial mobile platform with 16 benchmarks show that the IL approach successfully adapts the control policy to unknown applications. The explicit NMPC provides 25% energy savings compared to a state-of-the-art algorithm for multi-variable power management of modern GPU sub-systems.

Priority-aware networks-on-chip (NoCs) are used in industry to achieve predictable latency under different workload conditions. These NoCs incorporate deflection routing to minimize queuing resources within routers and achieve low latency during low traffic load. However, deflected packets can exacerbate congestion during high traffic load since they consume the NoC bandwidth. State-of-the-art analytical models for priority-aware NoCs ignore deflected traffic despite its significant latency impact during congestion. This paper proposes a novel analytical approach to estimate end-to-end latency of priority-aware NoCs with deflection routing under bursty and heavy traffic scenarios. Experimental evaluations show that the proposed technique outperforms alternative approaches and estimates the average latency for real applications with less than 8% error compared to cycle-accurate simulations.

Understanding user experience/satisfaction with mobile systems in order to manage computational resources has become a popular approach in recent years. One of the key challenges in this area is how to gauge user satisfaction. In this paper, we study the impact of CPU configuration on user satisfaction and power consumption with real users. Specifically, we propose a system to save energy by altering active CPU core count and frequency while keeping users satisfied. The system utilizes user-facing metrics such as frame rate and input lag to predict user satisfaction and then configure CPU core count and frequency in real-time to maximize satisfaction while minimizing power consumption. We first study a set of applications in-the-lab and show that we can accurately model satisfaction with the collected user-facing metrics. We then go into-the-wild in order to evaluate the proposed system in real environments. In the wild, we build a user-independent (user-oblivious) and user-dependent (personal) model. Users test the two models and the default scheme for one-week duration, which composes 140 days of worth of data. When compared to default scheme, our results show that, without impacting satisfaction, user-independent and user-dependent models save 12.3% and 11.8% of total system energy on average, respectively.

This paper introduces a predictive modeling framework for GPU performance. The key innovation underlying this approach is that performance statistics collected from representative workloads running on current generation GPUs can effectively predict the performance of next-generation GPUs. This is useful when simulators are available for the next-generation device, but simulation times are exorbitant, rendering early design space exploration of microarchitectural parameters and other features infeasible. When predicting performance across three Intel GPU generations (Haswell, Broadwell, Skylake), our models achieved impressively low out-of-sample-errors ranging from 7.45% to 8.91%, while running 29 481 to 44 214 times faster than cycle-accurate simulations. A detailed ranking of the most impactful features selected for these models provides an insight as to which microarchitectural subsystems have the greatest impact on performance from one generation to the next.

Networks-on-chip (NoCs) have become the standard for interconnect solutions in industrial designs ranging from client CPUs to many-core chip-multiprocessors. Since NoCs play a vital role in system performance and power consumption, pre-silicon evaluation environments include cycle-accurate NoC simulators. Long simulations increase the execution time of evaluation frameworks, which are already notoriously slow, and prohibit design-space exploration. Existing analytical NoC models, which assume fair arbitration, cannot replace these simulations since industrial NoCs typically employ priority schedulers and multiple priority classes. To address this limitation, we propose a systematic approach to construct priority-aware analytical performance models using micro-architecture specifications and input traffic. Our approach decomposes the given NoC into individual queues with modified service time to enable accurate and scalable latency computations. Specifically, we introduce novel transformations along with an algorithm that iteratively applies these transformations to decompose the queuing system. Experimental evaluations using real architectures and applications show high accuracy of 97% and up to 2.5× speedup in full-system simulation.

Dynamic resource management techniques rely on power consumption and performance models to optimize the operating frequency and utilization of processing elements, such as CPU and GPU. Despite the importance of these decisions, many existing approaches rely on fixed power and performance models that are learned offline. However, offline models cannot guarantee accuracy when workloads differ significantly from the training available at design time. This paper presents an online learning framework (STAFF) that constructs adaptive run-time models for stationary and non-stationary workloads. STAFF is the first framework that (1) guarantees stability while quickly adapting to workload changes, (2) performs online feature selection with linear complexity, and (3) adapts to new model coefficients by employing adaptively varying forgetting factor, all at the same time. Experiments on an Intel® Coreh™ i5 6th generation platform demonstrate up to 6× improvement in the performance prediction accuracy compared to existing techniques.

Approximately 18 percent of the 3.2 million smartphone applications rely on integrated graphics processing units (GPUs) to achieve competitive performance. Graphics performance, typically measured in frames per second, is a strong function of the GPU frequency, which in turn has a significant impact on mobile processor power consumption. Consequently, dynamic power management algorithms have to assess the performance sensitivity to the frequency accurately to choose the operating frequency of the GPU effectively. Since the impact of GPU frequency on performance varies rapidly over time, there is a need for online performance models that can adapt to varying workloads. This paper presents a light-weight adaptive runtime performance model that predicts the frame processing time of graphics workloads at runtime without apriori characterization. We employ this model to estimate the frame time sensitivity to the GPU frequency, i.e., the partial derivative of the frame time with respect to the GPU frequency. The proposed model does not rely on any parameter learned offline. Our experiments on commercial platforms with common GPU benchmarks show that the mean absolute percentage error in frame time and frame time sensitivity prediction are 4.2 and 6.7 percent, respectively.

In this work, we present a control-theoretic algorithm to improve the energy efficiency of the GPU targeting deadline-driven graphics applications. Our algorithm dynamically controls multiple power knobs within the GPU (DVFS and number of active slices) that have different control time granularities. We developed a multi-rate predictive control to overcome the time granularity constraints in the control variables and reduce runtime overhead. To enable predictive control, we developed runtime analytical predictive models for performance and power of the GPU, that take input from hardware counters and temperature sensor readings. We evaluated our approach on the latest generation of Intel Core i5 platform. Our experimental results demonstrate significant average GPU energy savings of 25% compared to the state-of-the-art algorithm at negligible performance overhead.

This paper presents a predictive modeling framework for GPU performance. The key innovation underlying this approach is that performance statistics collected from representative workloads running on current generation GPUs can effectively predict the performance of next-generation GPUs. This is useful when simulators are available for the next-generation device, but simulation times are exorbitant, rendering early design space exploration of microarchitectural parameters and other features infeasible. When predicting performance across three Intel GPU generations (Haswell, Broadwell, Skylake), our models achieved low out-of-sample-errors ranging from 7.45% to 8.91%, while running 30,000-45,000 times faster than cycle-accurate simulation.

Frame rate has a direct impact on the energy consumption of smartphones: the higher the frame rate, the higher the power consumption. Hence, reducing display refreshes will reduce the power consumption. However, it is risky to manipulate frame rate drastically as it can deteriorate user satisfaction with the device. In this work, we introduce a screen management system that controls the frame rate on smartphone displays based on a model that detects user dissatisfaction due to display refreshes. This approach is based on understanding when higher frame rates are necessary, and providing lower frame rates —thus, saving power— if the lower rate is predicted not to cause user dissatisfaction. According to the results of our first user survey with 20 participants, individuals show highly varying requirements: while some users require high frame rates for the highest satisfaction, others are equally satisfied with lower frame rates. Based on this observation, we develop a system that predicts user dissatisfaction on the runtime and either increases or decreases the maximum frame rate setting. For user dissatisfaction predictions, we have compared two different approaches: (1) static model, which uses dissatisfaction characteristics of a fixed group of people, and (2) user-specific model, which is learning only from the specific user. Our second set of experiments with 20 participants shows that users report 32% less dissatisfaction and 4% more dissatisfaction than the default Android system with user-specific and static systems, respectively. These experiments also show that, compared to the default scheme, our mechanisms reduce the power consumption of the phone by 7.2% and 1.8% on average with the user-specific and static models, respectively.

Integrated GPUs have become an indispensable component of mobile processors due to the increasing popularity of graphics applications. The GPU frequency is a key factor both in application throughput and mobile processor power consumption under graphics workloads. Therefore, dynamic power management algorithms have to assess the performance sensitivity to the GPU frequency accurately. Since the impact of the GPU frequency on performance varies rapidly over time, there is a need for online performance models that can adapt to varying workloads. This paper presents a light-weight adaptive runtime performance model that predicts the frame processing time. We use this model to estimate the frame time sensitivity to the GPU frequency. Our experiments on a mobile platform running common GPU benchmarks show that the mean absolute percentage error in frame time and frame time sensitivity prediction are 3.8% and 3.9%, respectively.

Modern smartphones and tablets are battery-constrained by their mobility; this constraint is heavily factored into any design decision made on the device. Furthermore, the display is one of the most power-consuming subsystems. Adaptive display brightness systems attempt to address this high display power consumption by setting the brightness depending on the surrounding ambient light levels.

This paper presents a control-theoretic approach to optimize the energy consumption of integrated CPU and GPU subsystems for graphic applications. It achieves this via a dynamic management of the CPU and GPU frequencies. To this end, we first model the interaction between the GPU and CPU as a queuing system. Second, we formulate a Multi-Input-Multi-Output state-space closed loop control to ensure robustness and stability. We evaluated this control on an Intel Baytrail-based Android platform. Experimental evaluations show energy savings of 17.4% in the CPU-GPU subsystem with a low performance impact of 0.9%.

Design automation has been one of the main propellers of the semiconductor industry with logic synthesis being one of the core technologies in this field. This article reviews the evolution of logic synthesis until the advent of techniques for automatic pipelining based on elastic timing, either synchronous or asynchronous. The emergence of these techniques can enable a productive interaction with tools that can do microarchitectural exploration of complex designs.

The display remains the primary user interface on many computing devices, ranging from traditional devices such as desktops and laptops, to the more pervasive devices such as smartphones and smartwatches. Thus, the overall user experience with these computing devices is greatly determined by the display subsystem. Ideal display brightness is critical to good user experience, but actually predicting the ideal brightness level which would most satisfy the user is a challenge. Finding the right screen brightness is even more challenging on mobile devices (which is the focus of this work), as the screen tends to be one of the most power consuming components. Currently, the control of display brightness is usually done through a simplistic, static one-size-fits-all model which chooses a fixed brightness level for a given ambient light condition.

As the core count in processor chips grows, so do the on-die, shared resources such as on-chip communication fabric and shared cache, which are of paramount importance for chip performance and power. This paper presents a method for dynamic voltage/frequency scaling of networks-on-chip and last level caches in multicore processor designs, where the shared resources form a single voltage/frequency domain. Several new techniques for monitoring and control are developed, and validated through full system simulations on the PARSEC benchmarks. These techniques reduce energy-delay product by 56% compared to a state-of-the-art prior work.

Power consumption has been one of the major design considerations for more than a decade [6]. Hence, energy efficient techniques have been widely studied to harness the processing power within available power and thermal budgets [3][4][10]. With the proliferation of smart mobile devices, the criticality of energy efficiency is multiplied. On one hand, increasing computational power as well as sensing, storage, and communication capabilities open up wide range of power-hungry application domains. On the other hand, the battery life rises as one of the major concerns of the end user [9]. Furthermore, these fanless devices are subject to tight surface, or skin, temperature constraints which limit the peak power consumption, since the skin temperature directly affects the user experience (UX). As a result, power management techniques crafted specifically for smart mobile devices become necessary. In this paper, we review three differentiating aspects for managing the power of smart mobile devices. More specifically, we emphasize the importance of platform view, user experience and platform level optimization.

In chip design today and for a foreseeable future, the last-level cache and on-chip interconnect is not only performance critical but also a substantial power consumer. This work focuses on employing dynamic voltage and frequency scaling (DVFS) policies for networks-on-chip (NoC) and shared, distributed last-level caches (LLC). In particular, we consider a practical system architecture where the distributed LLC and the NoC share a voltage/frequency domain that is separate from the core domain. This architecture enables the control of the relative speed between the cores and memory hierarchy without introducing synchronization delays within the NoC. DVFS for this architecture is more complex than individual link/core-based DVFS since it involves spatially distributed monitoring and control. We propose an average memory access time (AMAT)-based monitoring technique and integrate it with DVFS based on PID control theory. Simulations on PARSEC benchmarks yield a 27% energy savings with a negligible impact on system performance.

We present a compositional approach to formally verify quality-of-service (QoS) properties of network-on-chip (NoC) designs. A major challenge to scalability is the need to verify latency bounds for hundreds to thousands of cycles, which are beyond the capacity of state-of-the-art model checkers. We address this challenge by a compositional form of k-induction. The overall latency bound problem is divided into a number of sub-problems, termed latency lemmas. Each latency lemma states that a packet spends a smaller number of cycles at a particular “stage” of progress. We present a partially-automated method of computing these stages based on the topology of the network and a subset of relevant state, and verify the latency lemmas using k-induction. The effectiveness of this compositional technique is demonstrated on illustrative examples as well as an industrial ring interconnection network.

In chip design today and for a foreseeable future, on-chip communication is not only a performance bottleneck but also a substantial power consumer. This work focuses on employing dynamic voltage and frequency scaling (DVFS) policies for networks-on-chip (NoC) and shared, distributed last-level caches (LLC). In particular, we consider a practical system architecture where the distributed LLC and the NoC share a voltage/frequency domain which is separate from the core domain. This architecture enables controlling the relative speed between the cores and memory hierarchy without introducing synchronization delays within the NoC. DVFS for this architecture is more difficult than individual link/core-based DVFS since it involves spatially distributed monitoring and control. We propose an average memory access time (AMAT)-based monitoring technique and integrate it with DVFS based on PID control theory. Simulations on PARSEC benchmarks yield a 33% dynamic energy savings with a negligible impact on system performance.

With the scaling of process technologies, communication delays represent a bottleneck for the performance of circuits. One of the main issues that has to be handled is the variability of such delays. Latency-insensitive circuits offer a form of elast

Elasticity is a paradigm that tolerates the variations in computation and communication delays. By applying elastic transformations that allow varying the original timing, circuits can be optimized beyond the conventional rigid transformations that do not modify the external timing. Pipelining is one of the classical techniques to improve the throughput of a circuit. This article reveals how elasticity can be effectively and practically used to derive pipelined circuits by using correct-by-construction transformations that can be fully automated. Two designs, one of them industrial, are used to demonstrate how the area-performance trade-off can be explored using elasticity.

This paper presents a method for automatic microarchitectural pipelining of systems with loops. The original specification is pipelined by performing provably-correct transformations including conversion to a synchronous elastic form, early evaluation, inserting empty buffers, anti-tokens, and retiming. The design exploration is done by solving an optimization problem followed by simulation of solutions. The method is explained on a DLX microprocessor example. The impact of different microarchitectural parameters on the performance is analyzed.

Elastic systems, either synchronous or asynchronous, can be optimized for the average-case performance when they have units with early evaluation or variable latency. The performance evaluation of such systems using analytical methods is a complex problem and may become a bottleneck when an extensive exploration of different architectural configurations must be done. This paper proposes an analytical method for performance evaluation using symbolic expressions. Two version of the method are presented: an exact method that has high run time complexity and an efficient approximate method that computes the lower bound of the system throughput.

Elastic systems provide tolerance to the variations in computation and communication delays. The incorporation of elasticity opens new opportunities for optimization using new correct-by-construction transformations that cannot be applied to rigid non-elastic systems. The basics of synchronous and asynchronous elastic systems will be reviewed. A set of behavior-preserving transformations will be presented: retiming, recycling, early evaluation, variable-latency units and speculative execution. The application of these transformations for performance and power optimization will be discussed. Finally, a novel framework for microarchitectural exploration will be introduced, showing that the optimal pipelining of a circuit can be automatically obtained by using the previous transformations.

The architecture definition, design, and validation of the interconnect networks is a key step in the design of modern on-chip systems. This paper proposes a mathematical formulation of the problem of simultaneously defining the topology of the network and the message routes for the traffic among the processing elements of the system. The solution of the problem meets the physical and performance constraints defined by the designer. The method guarantees that the generated solution is deadlock free. It is also capable of automatically discovering topologies that have been previously used in industrial systems. The applicability of the method has been validated by solving realistic size interconnect networks modeling the typical multiprocessor systems.

The theory of regions was introduced in the early nineties as a method to bridge state and event-based models. This paper tackles the problem of deriving a Petri net from a state-based model, using the theory of regions. Some of the restrictions required in the traditional approach are dropped in this paper, together with significant extensions that make the approach applicable in new scenarios. One of these scenarios is Process Mining, where accepting (discovering) additional behavior in the synthesized Petri net is sometimes valued. The algorithmic emphasis used in this paper contributes to the demystification of the theory of regions as been only a good theoretical exercise, opening the door for its application in the industrial domain.

Retiming and recycling are two transformations used to optimize the performance of latency-insensitive (a.k.a. synchronous elastic) systems. This paper presents an approach that combines these two transformations for performance optimization of elastic systems with early evaluation. The method is based on Mixed Integer Linear Programming.

Speculation is a well-known technique for increasing parallelism of the microprocessor pipelines and hence their performance. While implementing speculation in modern design practice is error-prone and mostly ad-hoc, this paper proposes a correct-by-construction method for implementing speculation in Elastic Systems. The technique is based on applying provably correct transformations. The benefits of speculation are illustrated with two examples in which these transformations are systematically applied. The method proposed in this paper is amenable for automation in a synthesis flow.

Variable-latency designs may improve the performance of those circuits in which the worst-case delay paths are infrequently activated. Telescopic units emerged as a scheme to automatically synthesize variable-latency circuits. In this paper, a novel approach is proposed that brings three main contributions with regard to the methods used for telescopic units: first, no multi-cycle timing analysis is required to ensure the correctness of the circuit; second, the method can be applied to large circuits; third, the circuit can be optimized for the most frequent input patterns. The approach is based on finding approximations of critical nodes in the netlist that substitute the exact behavior. Two cycles are required when the approximations are not correct. These approximations can be obtained by the simulation of traces applied to the circuit. Experimental results on selected examples show a tangible speed-up (15%) with a small area overhead (3%).

Logic decomposition has been extensively used to optimize the worst-case delay and the area in the technology independent phase. Bi-decomposition is one of the state-of-art techniques to reduce the depth of the netlist due to the affordable computational cost. We present a novel n-way decomposition technique that improves bi-decomposition. The problem of decomposition is formulated as a Boolean relation which captures a larger set of possible solutions compared to bi-decomposition. The solution obtained from the Boolean relation improves the delay with near-zero cost in area. As it is shown on the experimental results, a considerable improvement is achieved on large netlists and even larger depending on which technology mapper is used.

A Boolean relation can specify some types of flexibility of a combinational circuit that cannot be expressed with don't cares. Several problems in logic synthesis, such as Boolean decomposition or multilevel minimization, can be modeled with Boolean relations. However, solving Boolean relations is a computationally expensive task. This paper presents a novel recursive algorithm for solving Boolean relations. The algorithm has several features: efficiency, wide exploration of solutions, and customizable cost function. The experimental results show the applicability of the method in logic minimization problems and tangible improvements with regard to previous heuristic approaches.

Elasticity in circuits and systems provides tolerance to variations in computation and communication delays. This paper presents a comprehensive overview of elastic circuits for those designers who are mainly familiar with synchronous design. Elasticity can be implemented both synchronously and asynchronously, although it was traditionally more often associated with asynchronous circuits. This paper shows that synchronous and asynchronous elastic circuits can be designed, analyzed, and optimized using similar techniques. Thus, choices between synchronous and asynchronous implementations are localized and deferred until late in the design process.

This paper presents a method for correct-by-construction microarchitectural pipelining that handles cyclic systems with dependencies between iterations. Our method combines previously known bypass and retiming transformations with a few transformations valid only for elastic systems with early evaluation (namely, empty FIFO insertion, FIFO capacity sizing, insertion of anti-tokens, and introducing early evaluation multiplexors). By converting the design to a synchronous elastic form and then applying this extended set of transformations, one can pipeline a functional specification with an automatically generated distributed controller that implements stalling logic resolving data hazards off the critical path of the design. We have developed an interactive toolkit for exploring elastic microarchitectural transformations. The method is illustrated by pipelining a few simple examples of instruction set architecture ISA specifications.

This paper presents a new tool for SystemVerilog RTL modifications with on-the-fly validation of local RTL changes. The tool, SV-rewrite, imports an initial version of SystemVerilog RTL and elaborates it into a hierarchical design description visualized as structural diagrams. From the design cockpit the user can select any set of visualized components, open a favorite text editor, modify then validate the new RTL description, and finally substitute this new rewritten RTL into the larger model to replace the originally selected components. This process of local validated rewrites can be repeated until the entire RTL is safely rewritten. We studied RTL abstraction using SV-rewrite to abstract the Pentium 80602 (P54CS) integer execution unit and register file. We have produced a significantly more readable RTL that is 2 to 3 times smaller than the original one. The abstracted RTL was validated by booting Linux on an FPGA-based emulation platform.

A protocol for latency-insensitive design with early evaluation is presented. The protocol is based on a symmetric view of the system in which tokens carrying information move in the forward direction and anti-tokens canceling information move in the backward direction. An implementation of the protocol and an example illustrate the flow for converting a regular synchronous design into an elastic circuit with early evaluation.

Retiming, c-slow retiming and recycling are different transformations for the performance optimization of sequential circuits. For retiming and c-slow retiming, different models that provide exact solutions have already been proposed. An exact model for recycling was yet unknown. This paper presents a general formulation that covers the combination of the three schemes for performance optimization. It provides an exact model based on integer linear programming that resorts to the structural theory of marked graphs. A set of experiments has been designed to show the benefits in performance obtained by combining retiming and recycling. The results also show the applicability of the method in large circuits.

A simple protocol for latency-insensitive design is presented. The main features of the protocol are the efficient implementation of elastic communication channels and the automatable design methodology. With this approach, fine-granularity elasticity can be introduced at the level of functional units (e.g. ALUs, memories). A formal specification of the protocol is defined and an efficient scheme for the implementation of elasticity that involves no datapath overhead is presented. The opportunities this protocol opens for microarchitectural design are discussed.

We formally define - at the stream transformer level - a class of synchronous circuits that tolerate any variability in the latency of their environment. We study behavioral properties of networks of such circuits and prove fundamental compositionality results. The paper contributes to bridging the gap between the theory of latency-insensitive systems and the correct implementation of efficient control structures for them

Most of the logic synthesis algorithms are not scalable for large networks and, for this reason, partitioning is often applied. However traditional mincut-based partitioning techniques are not always suitable for delay and area logic optimizations. The paper presents an approach that uses a dominator-based partitioning and conventional logic synthesis techniques for delay optimization of large networks. The calculation of dominators is crucial to find topologically ordered clusters suitable for logic restructuring. As a result, a scalable and efficient strategy for delay optimization is proposed and evaluated, showing tangible improvements with respect to existing techniques. A comparison with a standard mincut-based partitioning technique is also presented.

Early evaluation allows to execute operations when enough information at the inputs has been received to determine the value at the outputs. Systems that can tolerate variable-latency units, such as latency-insensitive or asynchronous systems, can enhance their performance by using early evaluation. The most relevant example of a unit with early evaluation is the multiplexor: the output can be determined as soon as the information of the selected channel arrives, without waiting for the other channels.

A recursive algorithm for solving Boolean relations is presented. It provides several features: wide exploration of solutions, parametrizable cost function and efficiency. The experimental results show the applicability of the method and tangible improvements with regard to previous heuristic approaches.

High performance microprocessor designs are partially characterized by functional blocks consisting of a large number of operations that are packed into very few cycles (often single-cycle) with little or no resource constraints but tight bounds on the cycle time. Extreme parallelization, conditional and speculative execution of operations is essential to meet the processor performance goals. However, this is a tedious task for which classical high-level synthesis (HLS) formulations are inadequate and thus rarely used. In this paper, we present a new methodology for application of HLS targeted to such microprocessor functional blocks that can potentially speed up the design space exploration for microprocessor designs. Our methodology consists of a coordinated set of source-level and fine-grain parallelizing compiler transformations that targets these behavioral descriptions, specifically loop constructs in them and enables efficient chaining of operations and high-level synthesis of the functional blocks. As a case study in understanding the complexity and challenges in the use of HLS, we walk the reader through the detailed design of an instruction length decoder drawn from the Pentium-family of processors. The chief contribution of this paper is formulation of a domain-specific methodology for application of high-level synthesis techniques to a domain that rarely, if ever, finds use for it.

This paper presents a design flow for timed asynchronous circuits. It introduces lazy transitions systems as a new computational model to represent the timing information required for synthesis. The notion of laziness explicitly distinguishes between the enabling and the firing of an event in a transition system. Lazy transition systems can be effectively used to model the behavior of asynchronous circuits in which relative timing assumptions can be made on the occurrence of events. These assumptions can be derived from the information known a priori about the delay of the environment and the timing characteristics of the gates that will implement the circuit. The paper presents the necessary conditions to generate circuits and a synthesis algorithm that exploits the timing assumptions for optimization. It also proposes a method for back-annotation that derives a set of sufficient timing constraints that guarantee the correctness of the circuit.

A method for automating the synthesis of asynchronous control circuits from high level (CSP-like) and/or partial STG (involving only functionally critical events) specifications is presented.The method solves two key subtasks in this new, more flexible, design flow: handshake expansion, i.e. inserting reset events with maximum concurrency, and event reshuffling under interface and concurrency constraints, by means of concurrency reduction.In doing so, the algorithm optimizes the circuit both for size and performance.Experimental results show a significant increase in the solution space explored when compared to existing CSP-based or STG-based synthesis tools.

This paper describes a novel methodology for high performance asynchronous design based on timed circuits and on CAD support for their synthesis using relative timing. This methodology was developed for a prototype iA32 instruction length decoding and steering unit called RAPPID ("revolving asynchronous Pentium processor instruction decoder") that was fabricated and tested successfully. Silicon results show significant advantages-in particular, performance of 2.5-4.5 instructions per nS-with manageable risks using this design technology. RAPPID achieves three times faster performance and half the latency dissipating only half the power and requiring a minor area penalty as a comparable 400 MHz clocked circuit. Relative timing is based on user-defined and automatically extracted relative timing assumptions between signal transitions in a circuit and its environment. It supports the specification, synthesis, and verification of high-performance asynchronous circuits, such as pulse-mode circuits, that can be derived from an initial speed-independent specification. Relative Timing presents a "middle-ground" between clocked and asynchronous circuits, and is a fertile area for CAD development. We discuss possible directions for future CAD development.

This paper describes a method of synthesis of asynchronous circuits with relative timing. Asynchronous communication between gates and modules typically utilizes handshakes to ensure functionality. Relative timing assumptions in the form "event a occurs before event b" can be used to remove redundant handshakes and associated logic. This paper presents a method for automatic generation of relative timing assumptions from the untimed specification. These assumptions can be used for area and delay optimization of the circuit. A set of relative timing constraints sufficient for the correct operation of the circuit is back-annotated to the designer. Experimental results for control circuits of a prototype iA32 instruction length decoding and steering unit called RAPPID (Revolving Asynchronous Pentium(R)Processor Instruction Decoder) shows significant improvements in area and delay over speed-independent circuits.

Logic decomposition is a well-known problem in logic synthesis, but it poses new challenges when targeted to speed-independent circuits. The decomposition of a gate into smaller gates must preserve not only the functional correctness of a circuit but also speed independence, i.e., hazard freedom under unbounded gate delays. This paper presents a new method for logic decomposition of speed-independent circuits that solves the problem in two major steps: (1) logic decomposition of complex gates and (2) insertion of new signals that preserve hazard freedom. The method is shown to be more general than previous approaches and its effectiveness is evaluated by experiments on a set of benchmarks.

This paper presents a new technique for decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed method iteratively performs Boolean decomposition of each such gate F into a two-input combinational or sequential gate G available in the library and two gates H/sub 1/ and H/sub 2/ simpler than F, while preserving the original behavior and speed-independence of the circuit. To extract functions for H/sub 1/ and H/sub 2/ the method uses Boolean relations as opposed to the less powerful algebraic factorization approach used in previous methods. After logic decomposition, the overall library matching and optimization is carried out. Logic resynthesis, performed after speed-independent signal insertion for H/sub 1/ and H/sub 2/, allows for sharing of decomposed logic. Overall, this method is more general than the existing techniques based on restricted decomposition architectures, and thereby leads to better results in technology mapping.

Interfaces, by nature, are often asynchronous since they serve for connecting multiple distributed mod ules/agents without common clock. However, the most recent developments in the the ory of asynchronous design in the areas of specifications, mo dels, analysis, verification, synthesis, technology mapping, timing optimization and performanc e analysis are not widely known and r arely accepted by industry.

This paper introduces bzy Transitions Systems &zTSs).The notion of laziness exDlicitlv distinguishes behveen the enabling and the firing of an e;ent in"a transition system.LzTSS can be effectively used to model the behavior of asynchronous circuits in whicfi relative timing assumptions cm-be made on the occurrence of events.These assumptions can be derived from the information known a priori about fie de]ay of fie environment and the timing characteristics of the gates that will implement the circuit.The paper presents necessary conditions to synthesize circuits with a correct behavior under the given timing assumr3tions.Preliminary results show that significant area and performance improvements can be obtained by exploiting the extra "don't care" space implicitly provided by the Iazmess of the events.

This paper presents a novel method to derive a Petri net from any specification model that can be mapped into a state-based representation with arcs labeled with symbols from an alphabet of events (a Transition System, TS). The method is based on the theory of regions for Elementary Transition Systems (ETS). Previous work has shown that, for any ETS, there exists a Petri Net with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original Transition System. Our method extends and implements that theory by using the following three mechanisms that provide a framework for synthesis of safe Petri nets from arbitrary TSs. First, the requirement of isomorphism is relaxed to bisimulation of TSs, thus extending the class of synthesizable TSs to a new class called Excitation-Closed Transition Systems (ECTS). Second, for the first time, we propose a method of PN synthesis for an arbitrary TS based on mapping a TS event into a set of transition labels in a PN. Third, the notion of irredundant region set is exploited, to minimize the number of places in the net without affecting its behavior. The synthesis method can derive different classes of place-irredundant Petri Nets (e.g., pure, free choice, unique choice) from the same TS, depending on the constraints imposed on the synthesis algorithm. This method has been implemented and applied in different frameworks. The results obtained from the experiments have demonstrated the wide applicability of the method.

Asynchronous circuits operate correctly only under timing assumptions. Hence testing those circuits for delay faults is crucial. Previous work has shown that full-scan delay-fault testing of asynchronous circuits is feasible. In this work, we tackle the problem of partial-scan testing, which requires test-pattern generation on a sequential circuit. We show how this problem can be effectively reduced to a classical problem of stuck-at test-pattern generation for a related combinational circuit. The reduction is done in three steps. The first step reduces testing of an asynchronous sequential circuit, by using a partial-scan approach, to testing an object called an asynchronous net, in which feedback is allowed only inside asynchronous memory elements. We then decompose the problem of testing asynchronous nets into that of initializing memory elements (the second step), followed by robust path delay fault testing (the third step). We provide effective procedures to solve both the initialization and the test-pattern generation problem. The technique is complete, automated, and requires only partial scan of some memory element outputs.

This paper develops a theoretical framework for the hazard-free gate-level implementation of speed-independent circuits specified by event-based models, such as signal transition graphs (for processes with AND causality and input choice) or their extension, called change diagrams (which allow OR-causality). It presents sufficient conditions, called the generalized monotonous cover requirements, for a hazard-free circuit to be built within a standard implementation structure. This structure consists of two-level simple-gate combinational logic and a row of latches, either a C-element or an RS-latch. A set of semantic-preserving transformations is defined that can be applied to an original behavioral description of the circuit so as to produce its specification in the form that satisfies the monotonous cover requirement. The transformations are applied at the event-based representation level (to avoid state explosion) and proved to be effective. The main result of the paper is therefore twofold: 1) the proof that any speed-independent behavior can be implemented at the gate level without hazards and 2) an efficient method for constructing such an implementation. Experimental results show that the proposed method compares very favorably, in area and performance, to the previously known techniques.

Presents a new technique for the decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed method iteratively performs Boolean decomposition of each such gate F into a two-input combinational or sequential gate G, which is available in the library, and two gates H/sub 1/ and H/sub 2/, which are simpler than F, while preserving the original behavior and speed-independence of the circuit. To extract functions for H/sub 1/ and H/sub 2/, the method uses Boolean relations, as opposed to the less powerful algebraic factorization approach used in previous methods. After logic decomposition, overall library matching and optimization is carried out. Logic resynthesis, performed after speed-independent signal insertion for H/sub 1/ and H/sub 2/, allows for the sharing of decomposed logic. Overall, this method is more general than existing techniques based on restricted decomposition architectures, and thereby leads to better results in technology mapping.

Asynchronous circuits operate correctly only under timing assumptions. Hence testing those circuits for delay faults is crucial. The paper describes a three step method to detect possible delay faults in a sequential asynchronous circuit. The delays that are to be tested must be provided by the synthesis system. By using this information a set of paths in the circuit that must be tested is identified (step 1). For these paths the circuit is made acyclic by inserting at least one scan latch in every cycle (step 2). Then test patterns are generated for these paths (step 3). These test patterns consist of setup and initialization vectors and the final test vector. We provide effective procedures to solve both the initialization and the test pattern generation problem. The latter problem is solved by reduction to a classical problem of stuck-at test pattern generation for a related combinational circuit. Finally, a heuristic is proposed to determine which state variables must become part of a scan chain, or for which input variables the positive and negative phase must be driven independently in test mode. Experimental results shows that a high level of path delay fault testability can be achieved with partial scan.

State assignment problems still need satisfactory solutions to make asynchronous circuit synthesis more practical. A well-known example of such a problem is that of complete state coding (CSC), which happens when a pair of different states in a specification has the same binary encoding. A standard way to approach state coding conflicts is to insert new state signals into the original specification in such a way that the original behavior remains intact. This paper proposes a method which improves over existing approaches by coupling generality, optimality, and efficiency. The method is based on the use of a class of "ground objects", called regions, that play the role of a bridge between state-based specifications (transition systems, TS's) and event-based specifications (signal transition graphs, STG's), We need to deal with both types of specification because designers usually prefer a timing diagram-like notation, such as STG, while optimization and cost analysis work better at the state level. A region in a transition system is a set of states that corresponds to a place in an STG (or the underlying Petri net). Regions are tightly connected with a set of properties that are to be preserved across the state encoding process, namely, 1) trace equivalence between the original and the encoded specification, and 2) implementability as a speed-independent circuit. We will build on a theoretical body of work that has shown the significance of regions for such property-preserving transformations, and describe a set of algorithms aimed at efficiently solving the encoding problem. The algorithms have been implemented in a software tool called petrify. Unlike many existing tools, petrify represents the encoded specification as an STG. This significantly improves the readability of the result (compared to a state-based description in which concurrency is represented implicitly by interleaving), and allows the designer to be more closely involved in the synthesis process. The efficiency of the method is demonstrated on a number of "difficult" examples.

This paper proposes a state encoding method for asynchronous circuits based on the theory of regions. A region in a Transition System is a set of states that “behave uniformly” with respect to a given transition (value change of an observable signal), and is analogue to a place in a Petri net. Regions are tightly connected with a set of properties that must be preserved across the state encoding process, namely: (1) trace equivalence between the original and the encoded specification, and (2) implementability as a speed-independent circuit. We build on a theoretical body of work that has shown the significance of regions for such property-preserving transformations, and describe a set of algorithms aimed at efficiently solving the encoding problem. The algorithms have been implemented in a software tool called petrify. Unlike many existing tools, petrify represents the encoded specification as an STG, and thus allows the designer to be more closely involved in the synthesis process. The efficiency of the method is demonstrated on a number of “difficult” examples.

No abstract available.

This paper presents a method to synthesize labeled Petri nets from state-based models. Although state-based models (such as finite state machines) are a powerful formalism to describe the behavior of sequential systems, they cannot explicitly express the notions of concurrency, causality and conflict Petri nets can naturally capture these notions. The proposed method in based on deriving an elementary transition system (ETS) from a specification model. Previous work has shown that for any ETS there exists a Petri net with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original ETS. This paper presents the first known approach to obtain an ETS from a non-elementary TS and derive a place-irredundant Petri net. Furthermore, by imposing constraints on the synthesis method, different classes of Petri nets can be derived from the same reachability graph (pure, free choice, unique choice). This method has been implemented and efficiently applied in different frameworks: Petri net composition, synthesis of Petri nets from asynchronous circuits, and resynthesis of Petri nets.

Existing methods for synthesis of speedindependent circuits under unbounded delay model have difficulties in combining the generality of formal approach with the practicality of the implementation architectures used at the logic level.This paper presents a characteristic property of the state graph specification, called Monotonous Cover requirement, implying its hazard-free implementation within the standard structure of a two-level SOP logic and a row of latches.The overall synthesis procedure ensures satisfiability of this condition by applying the generalised state assignment approach.

Determining the cycle time and a critical cycle is a fundamental problem in the analysis of concurrent systems.We solve this problem using timing simulation of an underlying Signal Graph (an extension of Marked Graphs).For a Signal Graph with n vertices and m arcs our algorithm has the polynomial time complexity O(b 2 m), where b is the number of vertices with initially marked in-arcs (typically bn).The algorithm has a clear semantic and a low descriptive complexity.We illustrate the use of the algorithm by applying it to performance analysis of asynchronous circuits.