Energy efficiency is among the most important challenges for computing. There has been an increasing gap between the rate at which the performance of processors has been improving and the lower rate of improvement in energy efficiency. This paper answers the question of how to reduce energy usage in heterogeneous datacenters. It proposes a unified hierarchical scheduling using a D-Choices technique, which considers interference and heterogeneity. continuous upgrades and the integrated high-performance ‘big’ and energy-efficient ‘little’ cores. This results in datacenters becoming more heterogeneous and traditional job scheduling algorithms become suboptimal. To this end, we present a two-level hierarchical scheduler for datacenters that exploits increased server heterogeneity. It combines in a unified approach cluster and node level scheduling algorithms, and it can consider specific optimization objectives including job completion time, energy usage, and energy-delay-product (EDP). Its novelty lies in the unified approach and in modeling interference and heterogeneity. Experiments on a research cluster found that the proposed approach outperforms state-of-the-art schedulers by around 10% in job completion time, 39% in energy usage, and 42% in EDP. This paper demonstrated a unified approach as a promising direction in optimizing energy and performance for heterogeneous datacenters.

Guest Editors Introduction: Special Issue on Network-on-Chip Architectures of the Future (NoCArc

The design of a heterogeneous network-on-chip (NoC) based H.264 video decoder is proposed. A thorough investigation using a system simulator developed as the combination of a cycle accurate NoC simulator together with complete implementations of all the video decoder modules is presented. The target hardware platform is a multicore system-on-chip, where the cores were designed for specific functions that correspond to the modules of the video decoder. Because such cores have different sizes and aspect ratios, a heterogeneous NoC is employed to facilitate the communication between modules. This is different from the reference case of a homogeneous NoC based hardware platform, where all cores are general purpose processors with the same area and where the NoC is a regular mesh NoC. The investigation looks at the impact of core sizes and floorplan for a given technology node as well as at the performance variation across several technology nodes.

In multicore processor systems, being able to accurately predict the future provides new optimization opportunities, which otherwise could not be exploited. For example, an oracle able to predict a certain application's behavior running on a smart phone could direct the power manager to switch to appropriate dynamic voltage and frequency scaling modes that would guarantee minimum levels of desired performance while saving energy consumption and thereby prolonging battery life. Using predictions enables systems to become proactive rather than continue to operate in a reactive manner. This prediction-based proactive approach has become increasingly popular in the design and optimization of integrated circuits and of multicore processor systems. Prediction transforms from simple forecasting to sophisticated machine learning based prediction and classification that learns from existing data, employs data mining, and predicts future behavior. This can be exploited by novel optimization techniques that can span across all layers of the computing stack. In this survey paper, we present a discussion of the most popular techniques on prediction and classification in the general context of computing systems with emphasis on multicore processors. The paper is far from comprehensive, but, it will help the reader interested in employing prediction in optimization of multicore processor systems.

We present a field programmable gate array (FPGA) based implementation of the H.264 video decoder algorithm. The novelty of our design is that the communication between the decoder modules is done using a network-on-chip (NoC). This makes our design scalable and easily integrated within larger future NoC based systems, where the same hardware platform can host other algorithms such as compression, filtering, etc. Our primary objective is to study the achievable performance with a NoC based H.264 decoder solution. The design process involves primarily three main steps. First, the H.264 algorithm is split into eight different partitions, which are implemented as individual processing elements (PEs). These processing elements are attached to the routers of the regular mesh NoC and include: network abstraction layer (NAL) parser and entropy decoder, frame buffer and integer motion, inverse quantization inverse transform, intra prediction, luma sub-pixel motion, chroma sub-pixel motion, deblocking filter, and display driver. These PEs are described in VHDL with the first two being executed on Nios II softcores. The network-on-chip was generated with the Connect tool from Carnegie Mellon University and integrated within the top level design entity. Second, we specify the location of each of the PEs inside the regular mesh NoC. Because we use eight PEs, the NoC architecture needs to be a 3x3 regular mesh topology. When we specify the location of the PEs inside the mesh topology (i.e., specify the router to which a particular PE is attached), we effectively solve what is called the NoC mapping problem. To do that, we use manual mapping, which is done intelligently based on information about the internal structure of the decoding algorithm. This helps to reduce the number of routers that packets must travel through the network. Finally, the entire project is synthesized, placed, and routed with Quartus Prime Standard Edition 16.1 tool. The final design is tested and verified on the DE4 development board, which uses Altera's Stratix IV GX FPGA chip. The performance of the implementation at the time of the submission is that to decode 100 frames takes 33 seconds for a frame size of 192x144 pixels and to decode 100 frames takes 56 seconds for a resolution of 320x240 pixels per frame. Documentation and source codes of the entire project will be released to the public domain. We hope that this will enable other researchers to easily replicate and compare results to ours and that it will encourage and facilitate further research in the areas of image processing, computer vision, and advanced VHDL design and FPGAs.

In this paper, we describe a new teaching approach whose objective is to implement entrepreneurship-based learning. The proposed teaching approach is essentially a project-based approach, but, with two novel key components that give it the entrepreneurship emphasis. First, the main idea is to divide students into groups of four or five members and have each team go through the process of starting-up a company. This process tries to emulate all steps through which entrepreneurs go when a new start-up idea is taken from concept to product realization. These steps include proposing a novel start-up idea, writing a business plan, coming up with a solution, implementing and testing the solution, and reporting results. The only constraint of this “exercise” is that all start-up ideas must be related to the main topic of the course, which in our case is that of advanced hardware description language and field-programmable gate array (FPGA) digital design. As a second component, each student is required to maintain a so called individual reflective journal (IRJ). Students add new entries of about half a page each week to the IRJ, which plays the role of a diary. The objective of this component is to engage students in thinking about how the course activities tie into the three components of the KEEN framework: curiosity, connections, and creation of value. The projected outcomes of this teaching approach include: 1) help students to develop an entrepreneurial mindset, 2) foster creativity and self-learning, and 3) engage students more and enable them to be proactive and competition-aware.

We propose a new circuit level reliability evaluation methodology.The proposed methodology is based on a divide and conquer approach, which enjoys the benefits of device level accuracy and of block level efficiency.At the core of the reliability estimation engine lies a Monte Carlo algorithm which works with failure times modeled as Weibull and lognormal distributions for major wearout mechanisms: time dependent dielectric break down, negative bias temperature instability, electromigration, thermal cycling, and stress migration.As a case study, we demonstrate how the proposed reliability evaluation technique can be applied to a Network-on-Chip router to identify the most vulnerable subblocks, which represent the reliability bottlenecks of the router.

In this paper, we propose a new fault-tolerant and congestion-aware adaptive routing algorithm for Networks-on-Chip (NoCs). The proposed algorithm is based on the ball and-string model and employs a distributed approach based on partitioning of the regular NoC architecture into regions controlled by local monitoring units. Each local monitoring unit runs a shortest path computation procedure to identify the best routing path so that highly congested routers and faulty links are avoided while latency is improved. To dynamically react to continuously changing traffic conditions, the shortest path computation procedure is invoked periodically. Because this procedure is based on the ball-and-string model, the hardware overhead and computational times are minimal. Experimental results based on an actual Verilog implementation demonstrate that the proposed adaptive routing algorithm improves significantly the network throughput compared to traditional XY routing and DyXY adaptive algorithms.

We formulate the problem of energy consumption and reliability oriented application mapping on regular Network-on-Chip topologies. We propose a novel branch-and-bound based algorithm to solve this problem. Reliability is estimated by an efficient Monte Carlo algorithm based on the destruction spectrum of the network. Simulation results demonstrate that reliability can be improved without sacrificing much of energy consumption.

In this study, we propose the use of specialized influence models to capture the dynamic behavior of a Network-on-Chip (NoC). Our goal is to construct a versatile modeling framework that will help in the development and analysis of distributed and adaptive features for NoCs. As an application testbench, we use this framework to construct a design methodology for dynamic voltage and frequency scaling (DVFS). We also point out similarities of the proposed model with backpressure mechanisms that could be potentially exploited toward enhanced models for estimation and optimization of NoCs.

The runtime of classic sequential placement algorithms for FPGAs continues to represent a serious problem, aggravated by the continuous increase of FPGAs. The traditional way to parallelize the placement step is to use parallel distributed implementations run on a network of processors. This approach can suffer from significant communication and synchronization runtime overheads. To address that, we propose the use of multithreading for parallelization. The top level placement problem is decomposed into region-based placement sub-problems using four-way min-cut partitioning. These sub-problems are then processed in parallel by worker threads. The final solution, constructed using the results from all sub-problems, is further improved using a fast low-temperature annealing refinement step. Using this technique, we parallelize the simulated annealing based placement algorithm of VPR. The new parallel placement algorithm achieves an average speed-up of 2.5x using four threads, while the wirelength after placement and circuit delay after routing increased on average with 3.7% and 2.15% respectively.

This paper investigates achieving fault tolerance by adaptive remapping in the context of networks on chip. The problem of dynamic application remapping is formulated and an efficient algorithm is proposed to address single and multiple PE failures. The new algorithm can be used to dynamically react and recover from PE failures in order to maintain system functionality. The quality of results is similar to that achieved using simulated annealing but in significantly shorter runtimes.

We present timing-driven partitioning and simulated-annealing (SA)-based placement algorithms together with a detailed routing tool for three-dimensional (3-D) field-programmable gate array (FPGA) integration. The circuit is first divided into layers with a limited number of interlayer vias, and then placed on individual layers, while minimizing the delay of critical paths. We use our tool as a platform to explore the potential benefits, in terms of delay and wire length (WL), that 3-D technologies can offer for FPGA fabrics. Experimental results show, on average, a total decrease of 25% in WL and 35% in delay can be achieved over traditional two-dimensional chips, when ten layers are used in 3-D integration

Modern field programmable gate array (FPGA) architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such a great flexibility comes at a high cost in terms of area, delay, and power. The authors propose a new FPGA routing architecture that utilizes a mixture of hardwired and traditional flexible switches. The result is an about a 30% reduction in leakage power consumption, a 5% smaller area, and 20% shorter delays, which translates to a 25% increase in the clock frequency. Despite the increase in clock speeds, the overall power consumption is reduced.

We present timing-driven partitioning and simulated annealing based placement algorithms together with a detailed routing tool for 3D FPGA integration. The circuit is first divided into layers with limited number of inter-layer vias, and then placed on individual layers, while minimizing the delay of critical paths. We use our tool as a platform to explore the potential benefits in terms of delay and wire-length that 3D technologies can offer for FPGA fabrics. Experimental results show on average a total decrease of 21% in wire-length and 24% in delay, can be achieved over traditional 2D chips, when five layers are used in 3D integration.

This paper introduces a novel 3-Dimensional (3D) vertically integrated adaptive computing system. This 3D-SoftChip is a combination of state-of-the-art processing and interconnection technology. It comprises the vertical integration of two chips (a Configurable Array Processor and an Intelligent Configurable Switch) through indium bump 3D interconnections. The Configurable Array Processor (CAP) is an array of heterogeneous processing elements (PEs) while the Intelligent Configurable Switch (ICS) comprises a switch block, 32-bit dedicated RISC processor for control, on-chip program/data memory, data frame buffer along with a Direct Memory Access (DMA) controller. This paper introduces the 3D-Softchip architecture for real-time communication and multimedia signal processing as a next gene! ration computing system. The paper further describes the up-to-date HW/SW co-design and verification methodology including high level system modeling and architecture exploration of 3D-SoftChip using SystemC in order to determine the optimum hardware specification in the early design stage.

Modern FPGA architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such great flexibility comes at a high cost in terms of area, delay and power. We propose a new FPGA routing architecture\footnoteThis work was supported in part by a grant from NSF under contract CAREER CCF-0347891 that utilizes a mixture of hardwired and traditional flexible switches. The result is 24% reduction in leakage power consumption, 7% smaller area and 24% shorter delays, which translates to 30% increase in clock frequency. Despite the increase in clock speeds, the overall power consumption is %, including dynamic power, reduced by 8%.

In traditional field programmable gate array (FPGA) placement methods, there is virtually no coupling between placement and routing. Performing simultaneous placement and detailed routing has been shown to generate much better placement qualities, but at the expense of significant runtime penalties (Nag and Rutenbar, 1998). We propose a routing-aware partitioning-based placement algorithm for FPGAs in which a looser but effective coupling between the placement and routing stages is used. The placement engine incorporates a more accurate FPGA delay model and employs effective heuristics that minimize circuit delay. Delay estimations are obtained from routing profiles of selected circuits that are placed and routed using the timing-driven versatile place and route (TVPR) (Betz and Rose, 1997), (Marquardt et al., 2000). As a result, the delay predictions during placement more accurately resemble those observed after detailed routing, which in turn leads to better delay optimization. An efficient terminal alignment heuristic for delay minimization is applied during placement to further optimize the delay of the circuit. These two techniques help maintain harmony between placement and routing-delay optimization stages. Simulation results show that the proposed partitioning-based placement combined with more accurate delay models and the alignment heuristic can achieve postrouting circuit delays comparable to those obtained from TVPR, while achieving a fourfold speedup in total placement runtime. In another experiment, we augmented the original TVPR algorithm with the terminal alignment heuristic, and achieved, on average, a 5% improvement in circuit delay with negligible runtime penalty.

Summary form only given. We present efficient solutions for the noncontiguous linear placement of data paths for reconfigurable fabrics. A strip-based architecture is assumed for the reconfigurable fabric. A preorder tree-expression or a general graph is placed in a strip, which can have active and/or inactive preplaced cores representing blockages and/or cores available for reuse. Two very efficient algorithms are proposed to solve the simpler problem of noncontiguous placement with blockages but without core reuse for tree graphs. The linear ordering obtained with any of the above algorithms is used as input for a third efficient algorithm to solve the problem of noncontiguous placement with both active and inactive cores. A fourth algorithm is proposed to solve the problem of noncontiguous placement with both core and connectivity reuse. Simulations results are reported.

In this paper we propose a partitioning-based placement algorithm for FPGAs. The method incorporates simple, but effective heuristics that target delay minimization. The placement engine incorporates delay estimations obtained from previously placed and routed circuits using VPR [6]. As a result, the delay predictions during placement more accurately resemble those observed after detailed routing, which in turn leads to better delay optimization. An efficient terminal alignment heuristic for delay minimization is employed to further optimize the delay of the circuit in the routing phase. Simulation results show that the proposed technique can achieve comparable circuit delays (after routing) to those obtained with VPR while achieving a 7-fold speedup in placement runtime.

Presents statistical-timing driven partitioning for performance optimization. We show that by using the concept of node criticality we can enhance the Fiduccia-Mattheyses (FM) partitioning algorithm to achieve, on average, around 20% improvements in terms of timing, among partitions with the same cut size. By incorporating mechanisms for timing optimization at the partitioning level, we facilitate wire-planning at high levels of the design process.

In this paper we present multi-objective hMetis partitioning for simultaneous cutsize and circuit delay minimization. We change the partitioning process itself by introducing a new objective function that incorporates a truly path-based delay component for the most critical paths. To avoid semi-critical paths from becoming critical, the traditional slack based delay component is also included in the cost function. The proposed timing driven partitioning algorithm is built on top of the hMetis algorithm, which is very efficient. Simulations results show that 14% average delay improvement can be obtained. Smooth trade-off between cutsize and delay is possible in our algorithm.

In this paper we present an effective technique for compacting a large sequence of input vectors into a much shorter one so as to reduce the circuit-level simulation time by orders of magnitude and maintain the accuracy of the power estimates. In particular, we model the effects of complex spatiotemporal correlations and rise/fall time slopes on total power dissipation. As the results demonstrate, large compaction ratios of orders of magnitude can be obtained without significant loss (about 5%, on average) in the accuracy of power estimates.