With the growing demand for VLSI scaling, standard cell library generation becomes crucial process to enhance performance via design technology co-optimization (DTCO) and system technology co-optimization (STCO) exploration. In this work, we review existing methodologies and algorithms used for standard cell layout automation for sub-10nm nodes, categorized by their algorithmic approaches for transistor placement and internal cell routing.

The goal of this paper is to apply two groundbreaking scaling transformations from the computing packaging industry to internet routers: heterogeneous integration of High-Bandwidth Memories (HBMs) and chiplets, as well as in-package optics. We propose a novel internet router architecture that leverages these technologies to realize a petabit/sec router in a single integrated package. We first introduce a new Split-Parallel Switch (SPS) architecture that spatially splits (without processing) the incoming fibers and distributes them across smaller independent switches. Then, we design these smaller switches as novel shared-memory HBM switches. We show how a Parallel Frame Interleaving (PFI) algorithm packs traffic into frames and accesses the HBM banks in a cyclical staggered interleaved way to reach HBM peak data rates. We further explain why these new technologies represent a paradigm shift in the design of future internet routers. Finally, we highlight that power consumption may constitute the main scaling bottleneck.

We propose SO3-Cell, the first automatic standard cell layout generation framework that optimizes three key steps simultaneously using Mixed-Integer Linear Programming (MILP). SO3-Cell simultaneously performs circuit topology optimization, transistor placement, and internal cell routing to achieve an optimized layout solution. Our optimization objective is to minimize metal usage while enhancing cell layout flexibility within a given area.We introduce design space pruning techniques to mitigate the complexity of larger designs, such as a full adder, a reset flip-flop (FF), and a 2-bit FF. We successfully generate a layout for a 44-transistor 2-bit FF within 25,862 seconds, demonstrating the scalability and robustness of the SO3-Cell framework. We evaluate the block-level PPA impact of the proposed cell-layout improvements, demonstrating a 35.0% reduction in power, a 2.2% increase in frequency, and a 31.1% reduction in area.

Moore's law scaling is approaching physical limits, as indicated by the technology roadmap. Recent standard cell layout reductions rely on track height compression, which increases pin density and routing congestion. To address these challenges, design technology co-optimization (DTCO) was introduced. This paper explores how much track height can be compressed and how DTCO features can sustain layout scaling. To support this exploration, we developed an SMT-based cell synthesis tool that integrates gear ratio, M1 metal grid offset, local-interconnect source-drain (LISD) merging, adjustable gate cut lengths, and double-height architecture with pass-throughs, and various power delivery options.

As physical pitch scaling slows, efforts to match its pace by reducing standard cell height and sacrificing horizontal routing tracks have introduced placement and routing challenges, making the design of high-quality standard cell layouts increasingly crucial. However, existing cell metrics only focus on pin accessibility and are insufficient to address issues in advanced nodes (e.g., Power Delivery Networks (PDN), increased routing blockages, etc.). We propose Cell Layout Flexibility(Cell-Flex) metrics, novel metrics that evaluate flexibility of standard cell layouts. flexibility reflects the versatility of cell layouts to placement and routing demands, which influences optimizing block design. By using Cell-Flex metrics as objectives in designing cell layout, we achieve a 13.2% reduction in block area without increasing total Design Rule Violations (DRVs). We develop a Machine Learning (ML) model using Kolmogorov-Arnold Networks (KAN) that utilizes the Cell-Flex metrics as features to make DRV prediction. By adding Cell-Flex features, we improve accuracy from 0.65 to 0.79 and F1 score from 0.52 to 0.78, demonstrating that our metrics are important for DRV prediction and serve as robust indicators of cell layout quality.

Prior research in Federated Learning (FL) has primarily focused on a setting in which all client models are identical (model-homogeneous). However, in practice, client devices may be diverse and heterogeneous, ranging possibly from small devices (e.g. IoTs) to large devices (e.g. supercomputers), each device class possessing distinct computing power, memory capacities, and configurations (device-heterogeneity). In this paper, we take a substantial step forward by defining a new problem wherein clusters of heterogeneous devices, each possessing distinctive models, memory capacities, computational resources and FL configurations, collaborate to enhance each other's global model within the federated learning paradigm. In particular, we propose FedHD (Federated Learning for Heterogeneous Devices), a knowledge distillation (KD)-based approach to address this new problem setting. Our approach leverages heterogeneous ensembles from all device clusters, to transfer knowledge between these clusters using a publicly available unlabeled dataset hosted at the server. To maximize knowledge exchange, we introduce an adaptive weighting strategy that assigns weights to each cluster's ensembles (as teachers) based on their model sizes relative to others. The core insight is that larger ensembles are more effective as teachers when transferring knowledge to smaller models, while smaller models are less effective in instructing larger models. Our experimental results demonstrate that FedHD achieves state-of-the-art performance compared to several baselines across various datasets and model architectures.

Federated Learning (FL) has emerged as a promising paradigm for collaborative machine learning, while preserving user data privacy. Despite its potential, standard FL algorithms lack support for diverse heterogeneous device prototypes, which vary significantly in model and dataset sizes---from small IoT devices to large workstations. This limitation is only partially addressed by existing knowledge distillation (KD) techniques, which often fail to transfer knowledge effectively across a broad spectrum of device prototypes with varied capabilities. This failure primarily stems from two issues: the dilution of informative logits from more capable devices by those from less capable ones, and the use of a single integrated logits as the distillation target across all devices, which neglects their individual learning capacities and and the unique contributions of each device. To address these challenges, we introduce TAKFL, a novel KD-based framework that treats the knowledge transfer from each device prototype's ensemble as a separate task, independently distilling each to preserve its unique contributions and avoid dilution. TAKFL also incorporates a KD-based self-regularization technique to mitigate the issues related to the noisy and unsupervised ensemble distillation process. To integrate the separately distilled knowledge, we introduce an adaptive task arithmetic knowledge integration process, allowing each student model to customize the knowledge integration for optimal performance. Additionally, we present theoretical results demonstrating the effectiveness of task arithmetic in transferring knowledge across heterogeneous device prototypes with varying capacities. Comprehensive evaluations of our method across both computer vision (CV) and natural language processing (NLP) tasks demonstrate that TAKFL achieves state-of-the-art results in a variety of datasets and settings, significantly outperforming existing KD-based methods. Our code is released at https://github.com/MMorafah/TAKFL and the project website is available at https://mmorafah.github.io/takflpage .

Clustered federated learning (FL) has been shown to produce promising results by grouping clients into clusters. This is especially effective in scenarios where separate groups of clients have significant differences in the distributions of their local data. Existing clustered FL algorithms are essentially trying to group together clients with similar distributions so that clients in the same cluster can leverage each other's data to better perform federated learning. However, prior clustered FL algorithms attempt to learn these distribution similarities indirectly during training, which can be quite time consuming as many rounds of federated learning may be required until the formation of clusters is stabilized. In this paper, we propose a new approach to federated learning that directly aims to efficiently identify distribution similarities among clients by analyzing the principal angles between the client data subspaces. Each client applies a truncated singular value decomposition (SVD) step on its local data in a single-shot manner to derive a small set of principal vectors, which provides a signature that succinctly captures the main characteristics of the underlying distribution. This small set of principal vectors is provided to the server so that the server can directly identify distribution similarities among the clients to form clusters. This is achieved by comparing the similarities of the principal angles between the client data subspaces spanned by those principal vectors. The approach provides a simple, yet effective clustered FL framework that addresses a broad range of data heterogeneity issues beyond simpler forms of Non-IIDness like label skews. Our clustered FL approach also enables convergence guarantees for non-convex objectives.

An oft-cited open problem of federated learning is the existence of data heterogeneity among clients. One pathway to understanding the drastic accuracy drop in federated learning is by scrutinizing the behavior of the clients’ deep models on data with different levels of "difficulty", which has been left unaddressed. In this paper, we investigate a different and rarely studied dimension of FL: ordered learning. Specifically, we aim to investigate how ordered learning principles can contribute to alleviating the heterogeneity effects in FL. We present theoretical analysis and conduct extensive empirical studies on the efficacy of orderings spanning three kinds of learning: curriculum, anti-curriculum, and random curriculum. We find that curriculum learning largely alleviates non-IIDness. Interestingly, the more disparate the data distributions across clients the more they benefit from ordered learning. We provide analysis explaining this phenomenon, specifically indicating how curriculum training appears to make the objective landscape progressively less convex, suggesting fast converging iterations at the beginning of the training procedure. We derive quantitative results of convergence for both convex and nonconvex objectives by modeling the curriculum training on federated devices as local SGD with locally biased stochastic gradients. Also, inspired by ordered learning, we propose a novel client selection technique that benefits from the real-world disparity in the clients. Our proposed approach to client selection has a synergic effect when applied together with ordered learning in FL.

The objective of a leakage recovery step is to make use of positive slack and reduce power by performing appropriate standard-cell swaps such as threshold-voltage ( V th ) or channel-length reassignments. The resulting engineering change order netlist needs to be timing clean. Because this recovery step is performed several times in a physical design flow and involves long runtimes and high tool-license usage, previous works have proposed graph neural network–based frameworks that restrict feature aggregation to three-hop neighborhoods and do not fully consider the directed nature of netlist graphs. As a result, the intermediate node embeddings do not capture the complete structure of the timing graph. In this article, we propose DAGSizer , a framework that exploits the directed acyclic nature of timing graphs to predict cell reassignments in the discrete gate sizing task. Our DAGSizer (Sizer for DAGs) framework is based on a node ordering-aware recurrent message-passing scheme for generating the latent node embeddings. The generated node embeddings absorb the complete information from the fanin cone (predecessors) of the node. To capture the fanout information into the node embeddings, we enable a bidirectional message-passing mechanism. The concatenated latent node embeddings from the forward and reverse graphs are then translated to nodewise delta-delay predictions using a teacher sampling mechanism. With eight possible cell-assignments, the experimental results demonstrate that our model can accurately estimate design-level leakage recovery with an absolute relative error ε model under 5.4%. As compared to our previous work, GRA-LPO, we also demonstrate a significant improvement in the model mean squared error.

While gliomas have become the most common cancerous brain tumors, manual diagnoses from 3D MRIs are time-consuming and possibly inconsistent when conducted by different radiotherapists, which leads to the pressing demand for automatic segmentation of brain tumors. State-of-the-art approaches employ FCNs to automatically segment the MRI scans. In particular, 3D U-Net has achieved notable performance and motivated a series of subsequent works. However, their significant size and heavy computation have impeded their actual deployment. Although there exists a body of literature on the compression of CNNs using low-precision representations, they either focus on storage reduction without computational improvement or cause severe performance degradation. In this article, we propose a CNN training algorithm that approximates weights and activations using non-negative integers along with trained affine mapping functions. Moreover, our approach allows the dot-product operations to be performed in an integer-arithmetic manner and defers the floating-point decoding and encoding phases until the end of layers. Experimental results on BraTS 2018 show that our trained affine mapping approach achieves near full-precision dice accuracy with 8-bit weights and activations. In addition, we achieve a dice accuracy within 0.005 and 0.01 of the full-precision counterparts when using 4-bit and 2-bit precisions, respectively.

Deep learning is highly pervasive in today's data-intensive era. In particular, convolutional neural networks (CNNs) are being widely adopted in a variety of fields for superior accuracy. However, computing deep CNNs on traditional CPUs and GPUs brings several performance and energy pitfalls. Several novel approaches based on ASIC, FPGA, and resistive-memory devices have been recently demonstrated with promising results. Most of them target only the inference (testing) phase of deep learning. There have been very limited attempts to design a full-fledged deep learning accelerator capable of both training and inference. It is due to the highly compute- and memory-intensive nature of the training phase. In this article, we propose LiteCON , a novel analog photonics CNN accelerator. LiteCON uses silicon microdisk-based convolution, memristor-based memory, and dense-wavelength-division-multiplexing for energy-efficient and ultrafast deep learning. We evaluate LiteCON using a commercial CAD framework (IPKISS) on deep learning benchmark models including LeNet and VGG-Net. Compared to the state of the art, LiteCON improves the CNN throughput, energy efficiency, and computational efficiency by up to 32×, 37×, and 5×, respectively, with trivial accuracy degradation.

SMART NoCs achieve ultra-low latency by enabling single-cycle multiple-hop transmission via bypass channels. However, contention along bypass channels can seriously degrade the performance of SMART NoCs by breaking the bypass paths. Therefore, contention-free task mapping and scheduling are essential for optimal system performance. In this article, we propose an SMT (Satisfiability Modulo Theories)-based framework to find optimal contention-free task mappings with minimum application schedule lengths on 2D/3D SMART NoCs with mixed dimension-order routing. On top of SMT’s fast reasoning capability for conditional constraints, we develop efficient search-space reduction techniques to achieve practical scalability. Experiments demonstrate that our SMT framework achieves 10× higher scalability than ILP (Integer Linear Programming) with 931.1× (ranges from 2.2× to 1532.1×) and 1237.1× (ranges from 4× to 4373.8×) faster average runtimes for finding optimum solutions on 2D and 3D SMART NoCs and our 2D and 3D extensions of the SMT framework with mixed dimension-order routing also maintain the improved scalability with the extended and diversified routing paths, resulting in reduced application schedule lengths throughout various application benchmarks.

As technology nodes continue to advance relentlessly, geometric pitch scaling starts to slow down. In order to retain the trend of Moore’s law, design technology co-optimization (DTCO) and system technology co-optimization (STCO) are introduced together to continue scaling beyond 5 nm using pitch scaling, patterning, and novel 3-D cell structures [i.e., complementary-FET (CFET)]. However, numerous DTCO and STCO iterations are needed to continue block-level area scaling with considerations of physical layout factors: 1) various standard cell (SDC) library sets (i.e., different cell heights and conventional FET); 2) design rules (DRs); 3) back end of line (BEOL) settings; and 4) power delivery network (PDN) configurations. The growing turnaround time (TAT) among SDC design, DR optimization, and block-level area evaluation becomes one of the major bottlenecks in DTCO and STCO explorations. In this work, we develop a machine learning model that combines bootstrap aggregation and gradient boosting techniques to predict the sensitivity of minimum valid block-level area of various physical layout factors. We first demonstrate that the proposed model achieves 16.3% less mean absolute error (MAE) than the previous work for testing sets. Then, we show that the proposed model successfully captures the block-level area sensitivity of new SDC library sets, new BEOL settings, and new PDN settings with 0.013, 0.004, and 0.027 MAE, respectively. Finally, compared to the previous work, the proposed approach improves the robustness of predicting new circuit designs by up to 6.76%. The proposed framework provides more than$100\times $speedup compared to conventional DTCO and STCO exploration flows.

This paper proposes a new paradigm for learning a set of independent logical rules in disjunctive normal form as an interpretable model for classification. We consider the problem of learning an interpretable decision rule set as training a neural network in a specific, yet very simple two-layer architecture. Each neuron in the first layer directly maps to an interpretable if-then rule after training, and the output neuron in the second layer directly maps to a disjunction of the first layer rules to form the decision rule set. Our representation of neurons in this first rules layer enables us to encode both the positive and the negative association of features in a decision rule. State-of-the-art neural net training approaches can be leveraged for learning highly accurate classification models. Moreover, we propose a sparsity-based regularization approach to balance between classification accuracy and the simplicity of the derived rules. Our experimental results show that our method can generate more accurate decision rule sets than other state-of-the-art rule-learning algorithms with better accuracy-simplicity trade-offs. Further, when compared with uninterpretable black-box machine learning approaches such as random forests and full-precision deep neural networks, our approach can easily find interpretable decision rule sets that have comparable predictive performance.

With the relentless scaling of technology nodes, physical design engineers encounter non-trivial challenges caused by rapidly increasing design complexity, particularly in the routing stage. Back-end designers must manually stitch/modify all of the design rule violations (DRVs) that remain after automatic place-and-route (P&R), during the implementation of engineering change orders (ECOs). In this paper, we propose CoRe-ECO, a concurrent refinement framework for efficient automation of the ECO process. Our framework efficiently resolves pin accessibility-induced DRVs by simultaneously performing detailed placement, detailed routing, and cell replacement. In addition to perturbation-minimized solutions, our proposed SMT-based optimization framework also suggests the adoption of alternative master cells to better achieve DRV-clean layouts. We demonstrate that our framework successfully resolves from 33.3% to 100.0% (58.6% on average) of remaining DRVs on M1-M3 layers, across a range of benchmark circuits with various cell architectures, while also providing average total wirelength reduction of 0.003%.

In this article, we propose an automated standard cell synthesis framework, SP&R, which simultaneously solves P&R without deploying any sequential/separate operations, by a novel dynamic pin allocation scheme. The proposed SP&R utilizes the multiobjective optimization feature of satisfiability modulo theories (SMT) to obtain optimal cell layouts. To achieve practical scalability of the framework, we develop various search-space reduction techniques, including breaking symmetry, conditional assignment/localization, and cell/objective function partitioning. Compared to the previous work, SP&R achieves 20.8× to 131.7× runtime improvements on average across the design-rule sets. As a result, SP&R successfully produces cell layouts up to 36 field-effect transistors (FETs) and 27 nets within 1.75 h by orchestrating all innovative tactics together, resulting in the generation of a whole 7-nm standard cell library. Compared to the known layouts, our work improves cell size and # M2 tracks by 0.1 contacted poly pitch and 0.3 tracks, respectively.

With the relentless scaling of technology nodes, design technology co-optimization (DTCO) for the conventional (Conv.) cell structure is starting to reach its limitations due to limited routing resources, lateral p-n separations, and performance requirements. As a result, system technology co-optimization (STCO) has been proposed to exploit the benefits of 3-D architectures. Complementary-FET (CFET) technology, which stacks p-FET on n-FET or vice versa, can release the restriction of p-n separation and reduce in-cell routing congestion by enabling p-n direct connections. However, CFET standard cell (SDC) synthesis demands holistic considerations to maximize the area benefit of scaling at the block level due to the extremely limited routability that comes from the stacked structure and reduced cell height. In this article, we propose a satisfiability modulo theory (SMT)-based CFET SDC synthesis framework that simultaneously solves place-and-route to generate optimized layouts. We first demonstrate that the CFET structure achieves 10.94% and 21.27% reduction on average cell area and metal length, respectively, and 15.10% smaller block-level area compared to Conv. structure as scaling down to 3.5T architecture. For routability, the proposed constraint-based minimum pin length/minimum pin opening and objective-based edge-based pin-separation/M2 track use reduce up to 48% #DRVs at the block level compared to the previous work. Then, through extensive DTCO explorations on ground design rules and #BEOLs, 3.5T CFET SDCs achieve up to 6.50% smaller block-level areas than 4.5T CFET SDCs. Finally, with the assistance of STCO and DTCO, 3.5T CFET SDCs achieve 21.0% on average reduced block-level areas compared to 4.5T Conv. SDCs.

Standard cell synthesis requires careful engineering approaches to ensure routability across various digital IC designs since physical design (PD) for sub-7nm technology nodes demands holistic efforts to address urgent and nontrivial design challenges. The smaller number of routing tracks and more complex design rules due to the sophisticated multi-patterning technology make place-and-route (P&R) for designing a standard cell extremely hard and time-consuming. Many conventional approaches have been suggested for improving transistor-level P&R and pin accessibility, nonetheless insufficient because of the heuristic/divide-and-conquer manners. In this paper, we propose a novel framework, SP&R, which simultaneously solves P&R for designing standard cell's layout without deploying any sequential procedures (between place and route steps) by using dynamic pin allocation-based cell synthesis. The proposed SP&R utilizes the Optimization Modulo Theories (OMT), an extension of the Satisfiability modulo theories (SMT), to obtain optimal standard cell layout by virtue of SAT (Boolean Satisfiability)-based fast reasoning ability. We validate that our SP&R framework achieves 10.5% of reduction on average in terms of metal length compared to the sequential approach, through practical standard cell designs targeting sub-7nm technology nodes.

Finding a small subset of data whose linear combination spans other data points, also called column subset selection problem (CSSP), is an important open problem in computer science with many applications in computer vision and deep learning. There are some studies that solve CSSP in a polynomial time complexity w.r.t. the size of the original dataset. A simple and efficient selection algorithm with a linear complexity order, referred to as spectrum pursuit (SP), is proposed that pursuits spectral components of the dataset using available sample points. The proposed non-greedy algorithm aims to iteratively find K data samples whose span is close to that of the first K spectral components of entire data. SP has no parameter to be fine tuned and this desirable property makes it problem-independent. The simplicity of SP enables us to extend the underlying linear model to more complex models such as nonlinear manifolds and graph-based models. The nonlinear extension of SP is introduced as kernel-SP (KSP). The superiority of the proposed algorithms is demonstrated in a wide range of applications.

Most deep learning accelerators in the literature focus only on improving the design of inference phase. We propose a novel photonics-based backpropagation accelerator for high performance deep learning training. The proposed MEMTONIC architecture is a first-of-its-kind memristor-integrated photonics-based deep learning architecture for end-to-end training and prediction. We evaluate the architecture using a photonic CAD framework (IPKISS) on deep learning benchmark models including LeNet and VGG-Net. The proposed design achieves at least 35× acceleration in training time, 31× improvement in computational efficiency, and 45× energy savings compared to the state-of-the-art designs, without any loss of accuracy.

In heterogeneous multicore systems, the memory subsystem plays a critical role, since most core-to-core communications are conducted through the main memory. Memory efficiency has a substantial impact on system performance. Although memory traffic from multimedia cores generally manifests high row-buffer locality, which is beneficial to memory efficiency, the locality is often lost as memory streams are forwarded through networks-on-chip (NoC). Previous studies have discussed the techniques that improve memory visibility to reveal scattered row-buffer hit opportunities to the memory scheduler. However, extending local memory visibility introduces little benefit after the locality has been severely diluted. As the alternative approach, preserving row-buffer locality in the NoC has not been well explored. What is worse, it remains to be studied how to perform network traffic scheduling with the awareness of both memory efficiency and quality-of-service (QoS). In this article, we propose a router design with embedded row-index caches to enable locality-aware packet forwarding. The proposed design requires minor modifications to existing router microarchitecture and can be easily implemented with priority arbiters to integrate QoS support. Extensive evaluations show that the proposed design achieves higher memory efficiency than prior memory-aware routers, in addition to providing QoS support. On basis of extant QoS-aware routers, locality-aware forwarding helps to increase row-buffer hits by 58.32% and reduce memory latency by 14.45% on average. It also introduces a net reduction in DRAM and NoC energy cost by 27.82%.

Pin accessibility encounters nontrivial challenges due to the smaller number of routing tracks, higher pin density, and more complex design rules. Consequently, securing design rule-correct routability has become a critical bottleneck for sub-10-nm IC designs (particularly in the detailed routing stage) costing days of runtime. To reduce turnaround time, IC designers demand new design methodologies to analyze the routing feasibility of a given layout architecture (e.g., conditional design rules, pin assignment patterns, etc). There are several conventional methods capable of assessing routability that consider pin accessibility. However, precise diagnosis of unroutable layouts remains an open problem for IC design practitioners. In this article, we propose two novel frameworks that: 1) efficiently analyzes design rule-correct routability via an integer linear programming (ILP)-derived Boolean satisfiability (SAT) formulation written in light-weight conjunctive normal form, on top of multicommodity flow theory and 2) precisely diagnose explicit reasons for design-rule violations (DRVs) in the form of human-interpretable explanations, while specifying conflicting design rules with a physical location. While covering a variety of conditional design rules, we have refined our formulation by using SAT encoding techniques, supernode simplification, Boolean constraint propagation-based preprocessing, etc. We demonstrate that our routability analysis framework produces design rule-correct routability assessment within 0.02% of ILP runtime on average. Also, our routability diagnosis framework precisely examines DRVs, revealing design-rule conflicts for a variety of pin layouts and switchboxes. We show our frameworks scalability by utilizing practical benchmarks ranging up to 40000 grid-size layouts (i.e., 200 Htrack × 200 Vtrack), producing results within an hour.

In traditional viral marketing, the goal is to reach out to the maximum number of people. However, some studies have demonstrated that spreading a product indiscriminately in a network can cause some counter effect because it may reach people who evaluate it negatively. In this paper, we study how to make use of social networks to avoid negative people so that the 'positive effect' of viral marketing can be maximized, and this optimization problem is called Strengthening the Positive Effect (SPE). SPE has a non-monotone and non-submodular objective function, and it is NP-hard to be approximately solved with any positive factor. Although SPE is almost impossible to solve approximately, we make the pioneer contribution by discovering that: 1) The almost optimal solution is obtainable in some network; 2) For the general network, a polynomial algorithm that yields a multiplicative guarantee is also possible under a reasonable assumption. We test our solution on various realworld social networks with a comprehensive set of experiments. The result affirms that besides its performance analyzability, our solution is more scalable than the current heuristic.

Routability diagnosis has increasingly become the bottleneck in detailed routing for sub-10nm technology due to the limited tracks, high density, and complex design rules. The conventional ways to examine the routability of detailed routing are ILP- and SAT-based techniques. However, once we identify the routability, the diagnosis remains an open problem for physical designers. In this paper, we propose a novel framework, called ROAD, which diagnoses explicit reasons for routing failures. The proposed ROAD framework utilizes a diagnosis-friendly SAT formulation to represent design's layout and diagnoses the routability with SAT solving techniques. Based on the diagnosis, ROAD provides human-interpretable explanations for conflicted routing conditions. To show the practical value of our framework, we also generate comprehensive test-sets that enable exhaustive exploration of layouts based on Rent's rule. We demonstrate that ROAD successfully examines conflict causes for diverse pin layouts. Throughout extensive diagnosis, we also present several key findings for design failure. ROAD performs routability diagnosis within 2 minutes on average for 90 grids testsets, while diagnosing the exact causes of routing failures in terms of congestion and conditional design rules.

Recent works have demonstrated the promise of using resistive random access memory (ReRAM) to perform neural network computations in memory. In particular, ReRAM-based crossbar structures can perform matrix-vector multiplication directly in the analog domain, but the resolutions of ReRAM cells and digital/analog converters limit the precisions of inputs and weights that can be directly supported. Although convolutional neural networks (CNNs) can be trained with low-precision weights and activations, previous quantization approaches are either not amenable to ReRAM-based crossbar implementations or have poor accuracies when applied to deep CNNs on complex datasets. In this article, we propose a new CNN training and implementation approach that implements weights using a trained biased number representation , which can achieve near full-precision model accuracy with as little as 2-bit weights and 2-bit activations on the CIFAR datasets. The proposed approach is compatible with a ReRAM-based crossbar implementation. We also propose an activation-side coalescing technique that combines the steps of batch normalization, non-linear activation, and quantization into a single stage that simply performs a clipped-rounding operation. Experiments demonstrate that our approach outperforms previous low-precision number representations for VGG-11, VGG-13, and VGG-19 models on both the CIFAR-10 and CIFAR-100 datasets.

In modern heterogeneous MPSoCs, the management of shared memory resources is crucial in delivering end-to-end QoS. Previous frameworks have either focused on singular QoS targets or the allocation of partitionable resources among CPU applications at relatively slow timescales. However, heterogeneous MPSoCs typically require instant response from the memory system where most resources cannot be partitioned. Moreover, the health of different cores in a heterogeneous MPSoC is often measured by diverse performance objectives. In this work, we propose the Self-Aware Resource Allocation framework for heterogeneous MPSoCs. Priority-based adaptation allows cores to use different target performance and self-monitor their own intrinsic health. In response, the system allocates non-partitionable resources based on priorities. The proposed framework meets a diverse range of QoS demands from heterogeneous cores. Moreover, we present a runtime scheme to configure priority-based adaptation so that distinct sensitivities of heterogeneous QoS targets with respect to memory allocation can be accommodated. In addition, the priority of best-effort cores can also be regulated.

SMART-based NoC designs achieve ultra-low latencies by enabling flits to traverse multiple hops within a single clock cycle. Notwithstanding the clear performance benefits, SMART-based NoCs suffer from several shortcomings: each router must arbitrate among a quadratic number of requests, which leads to high costs; each router independently makes its own arbitration decisions, which leads to a problem called false negatives that causes throughput loss. In this article, we propose a new SMART-based NoC design called SHARP that overcomes these shortcomings. Our evaluation demonstrates that SHARP increases throughput by up to 19% and average link utilization by up to 24% by avoiding false negatives. By avoiding quadratic arbitration, our evaluation further demonstrates that SHARP reduces the wiring and area overhead significantly.

In heterogeneous multicore systems, the memory subsystem, including the last-level cache and DRAM, is widely shared among the CPU, the GPU, and the real-time cores. Due to their distinct memory traffic patterns, heterogeneous cores result in more frequent cache misses at the last-level cache. As cache misses travel through the memory subsystem, two schedulers are involved for the last-level cache and DRAM, respectively. Prior studies treated the scheduling of the last-level cache and DRAM as independent stages. However, with no orchestration and limited visibility of memory traffic, neither scheduling stage is able to ensure optimal scheduling decisions for memory efficiency. Unnecessary precharges and row activations happen in DRAM when the memory scheduler is ignorant of incoming cache misses, and DRAM row-buffer states are invisible to the last-level cache. In this article, we propose a unified memory controller for the the last-level cache and DRAM with orchestrated schedulers. The memory scheduler harvests row-buffer hit opportunities in cache request buffers during spare time without inducing significant implementation cost. We further introduce a dynamic orchestrated scheduling policy to improve memory efficiency while achieving target CPU IPC. Extensive evaluations show that the proposed controller improves the total memory bandwidth of DRAM by 16.8% on average and saves DRAM energy by up to 29.7% while achieving comparable CPU IPCs. With the dynamic scheduling policy, the unified controller achieves the same IPC as the conventional design and increases DRAM bandwidth by 9.2%. In addition, we explore the potential of the proposed memory controller to attain improvements on both memory bandwidth and CPU IPC.

In modern heterogeneous MPSoCs, the management of shared memory resources is crucial in delivering end-to-end QoS. Previous frameworks have either focused on singular QoS targets or the allocation of partitionable resources among CPU applications at relatively slow timescales. However, heterogeneous MPSoCs typically require instant response from the memory system where most resources cannot be partitioned. Moreover, the health of different cores in a heterogeneous MPSoC is often measured by diverse performance objectives. In this work, we propose the Self-Aware Resource Allocation (SARA) framework for heterogeneous MPSoCs. Priority-based adaptation allows cores to use different target performance and self-monitor their own intrinsic health. In response, the system allocates non-partitionable resources based on priorities. The proposed framework meets a diverse range of QoS demands from heterogeneous cores.

In heterogeneous multicore systems, the memory subsystem, including the last-level cache and DRAM, is widely shared among the CPU, the GPU, and the real-time cores. Due to their distinct memory traffic patterns, heterogeneous cores result in more frequent cache misses at the last-level cache. As cache misses travel through the memory subsystem, two schedulers are involved for the last-level cache and DRAM respectively. Prior studies treated the scheduling of the last-level cache and DRAM as independent stages. However, with no orchestration and limited visibility of memory traffic, neither scheduling stage is able to ensure optimal scheduling decisions for memory efficiency. Unnecessary precharges and row activations happen in DRAM when the memory scheduler is ignorant of incoming cache misses and DRAM row-buffer states are invisible to the last-level cache. In this paper, we propose a unified memory controller for the the last-level cache and DRAM with orchestrated schedulers. The memory scheduler harvests row-buffer hit opportunities in cache request buffers during spare time without inducing significant implementation cost. Extensive evaluations show that the proposed controller improves the total memory bandwidth of DRAM by 16.8% on average and saves DRAM energy by up to 29.7% while achieving comparable CPU IPC. In addition, we explore the impact of last-level cache bypassing techniques on the proposed memory controller.

Backpressure-based adaptive routing algorithms have been studied extensively in the literature. Although backpressure-based adaptive routing algorithms have been shown to be network-wide throughput optimal, they typically have poor delay performance under light or moderate loads because packets may be sent over unnecessarily long routes. Further, backpressure-based algorithms have required every node to compute differential backlogs for every destination queue with the corresponding destination queue at every adjacent node. This computation is expensive given the large number of possible pairwise differential backlogs and requires many exchanges of backlog information between adjacent nodes. In this paper, we propose new backpressure-based adaptive routing algorithms that only use shortest-path routes to destinations when they are sufficient to accommodate the given traffic load, but the proposed algorithms will incrementally expand routing choices as needed to accommodate increasing traffic loads. We show analytically by means of fluid analysis that the proposed algorithms retain network-wide throughput optimality, and we show empirically by means of simulations that our proposed algorithms provide substantial improvements in delay performance. Our evaluations further show that in practice, our approach dramatically reduces the number of pairwise differential backlogs that have to be computed and the amount of corresponding backlog information that has to be exchanged because routing choices are only incrementally expanded as needed.

Chang et al. proposed the load-balanced switch in their seminal work [1], which has received wide attention due to its inherent scalability properties in both size and speed. These scalability properties continue to be of significant interest due to the relentless exponential growth in Internet traffic. The main drawback of the load-balanced switch is that packets can depart out-of-order from the switch, which can significantly degrade network performance by negatively interacting with TCP congestion control. Hence, a large body of subsequent work has proposed a variety of modifications for ensuring packet ordering, but all the proposed approaches tend to increase packet delay significantly in comparison to the basic load-balanced switch. In this paper, we show that the amount of packet reordering that can occur with the load-balanced switch is actually quite limited, which means that packet reordering can simply be rectified by employing reordering buffers at the switch outputs. In particular, we formally bound the worst-case amount of time that a packet has to wait in these output reordering buffers before it is guaranteed to be ready for in-order departure with high probability, and we prove that this bound is linear with respect to the switch size. This linear bound is significant because previous approaches can add quadratic or cubic delays to the load-balanced switch. In addition, we use a hash-grouping method that further reduces resequencing delays significantly. Although simple and intuitive, our experimental results show that our output packet reordering approach substantially outperforms existing load-balanced switch architectures.

Heterogeneous MPSoCs typically integrate diverse cores, including application CPUs, GPUs, and HD coders. These cores commonly share an off-chip memory to save cost and energy, but their memory accesses often interfere with each other, leading to undesirable consequences like a slowdown of application performance or a failure to sustain real-time performance. The memory controller plays a central role in meeting the QoS needs of real-time cores while maximizing CPU performance. Previous QoS-aware memory controllers are based on a classic two-tier queuing architecture that buffers memory transactions at the first tier, followed by a second tier that buffers translated DRAM commands. In these designs, QoS-aware policies are used to schedule competing transactions at the first stage, but the translated DRAM commands are served in FIFO order at the second stage. Unfortunately, once the scheduled transactions have been forwarded to the command stage, newly arriving transactions that may be more critical cannot be served ahead of those translated commands that are already queued at the second stage. To address this, we propose a scalable memory controller architecture based on single-tier virtual queuing (STVQ) that maintains a single tier of request queues and employs an efficacious scheduler that considers both QoS requirements and DRAM bank states. In comparison with previous QoS-aware memory controllers, the proposed STVQ memory controller reduces CPU slowdown by up to 13.9% while satisfying all frame rate requirements. We propose further optimizations that can significantly increase row-buffer hits by up to 66.2% and reduce memory latency by up to 19.8%.

In heterogeneous MPSoCs, memory interference between the CPU and realtime cores is a critical impediment to system performance. Previous memory schedulers adopt the classic two-tier queuing system, but unfortunately the use of two-tier queuing deteriorates the QoS of scheduling policies. In this paper, we propose the Single-Tier Virtual Queuing (STVQ) memory controller for efficacious QoS-aware scheduling. The STVQ memory controller maintains single-tier transaction queues and employs separable allocation for transaction scheduling with high scalability. A multi-source realtime scheduling algorithm is further presented. The STVQ controller achieves up to 13.9% less CPU IPC slowdown than previous schedulers with no frame rate penalty on realtime cores.

We consider the design of a shared global on-chip communication medium using repeated equalized transmission lines (RETLs). Our design overcomes a number of limitations with previously proposed shared global mediums based on transmission lines. Prior solutions require wide-pitch transmission lines that occupy considerable area, do not support multicast or broadcast operations, and employ centralized schedulers that are difficult to scale. In this paper, we propose a novel design based on RETLs that utilizes thin transmission lines that require a much narrower pitch, about 6x narrower in comparison to previously proposed wide-pitch-based designs. In addition, our design supports multicast and broadcast operations, which are critical for the implementation of cache coherency protocols. Moreover, our design is based on fully distributed arbitration protocols that can achieve very high throughput and bandwidth utilization, but are simple to implement. We demonstrate a design using 32 lanes of 20 Gb/s differential RETLs that provides 640 Gb/s aggregated throughput and enables communications between any on-chip cores in under two core clock cycles, including multicast and broadcast communications. Given the narrow pitch of RETLs, our design can easily scale to multiple terabits per seconds with additional lanes. Simulation results with both synthetic and real benchmarks with up to 64 parallel threads demonstrate that our proposed distributed solutions are capable of achieving near ideal throughput.

Load-balanced switch architectures are known to be scalable in both size and speed, which is of interest due to the continued exponential growth in Internet traffic. However, the main drawback of load-balanced switches is that packets can depart out of order from the switch. Randomized load-balancing of application flows by means of hashing on the packet header is a well-known simple solution to this packet reordering problem in which all packets belonging to the same application flow are routed through the same intermediate port and hence the same path through the switch. Unfortunately, this method of load-balancing can lead to instability, depending on the mix of flow sizes and durations in the group of flows that gets randomly assigned to route through the same intermediate port. In this paper, we show that the randomized load-balancing of application flows can be enhanced to provably guarantee both stability and packet ordering by extending the approach with safety mechanisms that can uniformly diffuse packets across the switch whenever there is a build-up of packets waiting to route through the some intermediate port. Although simple and intuitive, our experimental results show that our extended randomized load-balancing approach significantly outperforms existing load-balanced switch architectures.

Network-wide traffic measurement is of interest to network operators to uncover global network behavior for the management tasks of traffic accounting, debugging or troubleshooting, security, and traffic engineering. Increasingly, sophisticated network measurement tasks such as anomaly detection and security forensic analysis are requiring in-depth fine-grained flow-level measurements. However, performing in-depth per-flow measurements (e.g., detailed payload analysis) is often an expensive process. Given the fast-changing Internet traffic landscape and large traffic volume, a single monitor is not capable of accomplishing the measurement tasks for all applications of interest due to its resource constraint. Moreover, uncovering global network behavior requires network-wide traffic measurements at multiple monitors across the network since traffic measured at any single monitor only provides a partial view and may not be sufficient or accurate. These factors call for coordinated measurements among multiple distributed monitors. In this paper, we present a centralized optimization framework, LEISURE (Load-EqualIzed meaSUREment), for load-balancing network measurement workloads across distributed monitors. Specifically, we consider various load-balancing problems under different objectives and study their extensions to support both fixed and flexible monitor deployment scenarios. We formulate the latter flexible monitor deployment case as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. We evaluate LEISURE via detailed simulations on Abilene and GEANT network traces to show that LEISURE can achieve much better load-balanced performance (e.g., 4.75× smaller peak workload and 70× smaller variance in workloads) across all coordinated monitors in comparison to a naive solution (uniform assignment) to accomplish network-wide traffic measurement tasks under the fixed monitor deployment scenario. We also show that under the flexible monitor deployment setting, our heuristic solutions can achieve almost the same load-balancing performance as the optimal solution while reducing the computation times by a factor up to 22.5× in Abilene and 800× in GEANT.

Internet traffic continues to grow exponentially, calling for switches that can scale well in both size and speed. While load-balanced switches can achieve such scalability, they suffer from a fundamental packet reordering problem. Existing proposals either suffer from poor worst-case packet delays or require sophisticated matching mechanisms. In this paper, we propose a new family of stable load-balanced switches called "Sprinklers" that has comparable implementation cost and performance as the baseline load-balanced switch, but yet can guarantee packet ordering. The main idea is to force all packets within the same virtual output queue (VOQ) to traverse the same ``fat path'' through the switch, so that packet reordering cannot occur. At the core of Sprinklers are two key innovations: a randomized way to determine the "fat path" for each VOQ, and a way to determine its "fatness" roughly in proportion to the rate of the VOQ. These innovations enable Sprinklers to achieve near-perfect load-balancing under arbitrary admissible traffic. Proving this property rigorously using novel worst-case large deviation techniques is another key contribution of this work.

Regular expression matching, a central task in deep packet inspection and other networking applications, has been traditionally implemented through finite automata. Thanks to their limited per-character processing and memory bandwidth requirements, deterministic finite automata (DFA) are a natural choice for memory-based implementations. In the presence of large datasets of complex patterns, however, DFA suffer from the well-known state explosion problem. Specifically, state explosion can take place during DFA generation when the considered patterns contain bounded and unbounded repetitions of wildcards or large character sets. Several alternative FA representations have been proposed to address this problem. However, these proposals all suffer from one or more of the following problems: some can avoid state explosion only on datasets of limited size and complexity; some have prohibitive worst-case memory bandwidth requirements or processing time; and some can only guarantee functional equivalence for restricted classes of regular expressions and require the user to manually filter out unsupported patterns. In this work we propose JFA, a finite automation that uses state variables to avoid state explosion, and is functionally equivalent to the corresponding DFA. Functional equivalence is guaranteed by construction without requiring user intervention. We also provide optimization techniques to both limit the amount of state variables required and provide a lower bound for the JFA traversal time.

High-performance routers need to temporarily store a large number of packets in response to congestion. DRAM is typically needed to implement large packet buffers, but the worst-case random access latencies of DRAM devices are too slow to match the bandwidth requirements of high-performance routers. Existing DRAM-based architectures for supporting linespeed queue operations can be classified into two categories: prefetching-based and randomization-based. They are all based on interleaving memory accesses across multiple parallel DRAM banks for achieving higher memory bandwidths, but they differ in their packet placement and memory operation scheduling mechanisms. In this paper, we describe novel reservation-based packet buffer architectures with interleaved memories that take advantage of the known packet departure times to achieve simplicity and determinism. The number of interleaved DRAM banks required to implement the proposed packet buffer architectures is independent of the number of logical queues, yet the proposed architectures can achieve the performance of an SRAM implementation. Our reservation-based solutions are scalable to growing packet storage requirements in routers while matching increasing line rates.

Accurate estimators of key design metrics (power, area, delay, etc.) are increasingly required to achieve IC cost reductions in system-level through physical layout optimizations. At the same time, identifying physical or analytical models of design metrics has become very challenging due to interactions among many parameters that span technology, architecture and implementation. Metamodeling techniques can simplify this problem by deriving surrogate models from samples of actual implementation data. However, the use of metamodeling techniques in IC design estimation is still in its infancy, and practitioners need more systematic understanding. In this work, we study the accuracy of metamodeling techniques across several axes: (1) low- and high-dimensional estimation problems, (2) sampling strategies, (3) sample sizes, and (4) accuracy metrics. To help obtain more general conclusions, we study these axes for three very distinct chip design estimation problems: (1) area and power of networks-on-chip routers, (2) delay and output slew of standard cells under power delivery network noise, and (3) wirelength and buffer area of clock trees. Our results show that (1) adaptive sampling can effectively reduce the sample size required to derive surrogate models by up to 64% (or, increase estimation accuracy by up to 77%) compared with Latin hypercube sampling; (2) for low-dimensional problems, Gaussian process-based models can be 1.5x more accurate than tree-based models, whereas for high-dimensional problems, tree-based models can be up to 6x more accurate than Gaussian process-based models; and (3) a variant of weighted surrogate modeling [7], which we call hybrid surrogate modeling, can improve estimation accuracy by up to 3x. Finally, to aid architects, design teams, and CAD developers in selection of the appropriate metamodeling techniques, we propose guidelines based on the insights gained from our studies.

In this paper, we study the problem of optimal oblivious routing for 1D and 2D torus networks. We introduce a new closed-form oblivious routing algorithm called W2TURN that is worst-case throughput optimal for 2D torus networks. W2TURN is based on a weighted random selection of paths that contain at most two turns. Restricting the maximum number of turns in routing paths to just two enables a simple deadlock-free implementation of W2TURN. In terms of average hop count, W2TURN outperforms the best previously known closed-form worst-case throughput optimal routing algorithm called IVAL [CHECK END OF SENTENCE]. When the network radix is odd, W2TURN achieves the minimum average hop count that can be achieved with 2-turn paths while remaining worst-case throughput optimal. When the network radix is even, W2TURN comes very close to achieving the minimum average hop count while remaining worst-case throughput optimal, within just 0.72 percent on a 12\times 12 torus. We also describe another routing algorithm based on weighted random selection of paths with at most two turns called I2TURN and show that I2TURN is equivalent to IVAL. However, I2TURN eliminates the need for loop removal at runtime and provides a closed-form analytical expression for evaluating the average hop count. The latter enables us to demonstrate analytically that W2TURN strictly outperforms IVAL (and I2TURN) in average hop count. Finally, we present a new optimal weighted random routing algorithm for rings called Weighted Random Direction (WRD). WRD provides a closed-form expression for the optimal distribution of traffic along the minimal and nonminimal directions in a ring topology to achieve minimum average hop count while guaranteeing optimal worst-case throughput. Based on our evaluations, in addition to being worst-case throughput optimal, W2TURN and WRD also perform well in the average case, and outperform the best previously known worst-case throughput optimal routing algorithms with closed-form descriptions in latency and throughput over a wide range of traffic patterns.

The papers in this special issue focus on quality of service in the network and services management sectors.

The choice of routing algorithm plays a vital role in the performance of on-chip interconnection networks. Adaptive routing is appealing because it offers better latency and throughput than oblivious routing, especially under nonuniform and bursty traffic. The performance of an adaptive routing algorithm is determined by its ability to accurately estimate congestion in the network. In this regard, maintaining global congestion state using a separate monitoring network offers better congestion visibility into distant parts of the network compared to solutions relying only on local congestion. However, the main challenge in designing such routing schemes is to keep the logic and bandwidth overhead as low as possible to fit into the tight power, area, and delay budgets of on-chip routers. In this article, we propose a minimal destination-based adaptive routing strategy (DAR), where every node estimates the delay to every other node in the network, and routing decisions are based on these per-destination delay estimates. DAR outperforms Regional Congestion Awareness (RCA), the best previously known adaptive routing algorithm that uses nonlocal congestion state. The performance improvement is brought about by maintaining fine-grained per-destination delay estimates in DAR that are more accurate than regional congestion metrics measured in RCA. The increased accuracy is a consequence of the fact that the per-destination delay estimates are not corrupted by congestion on links outside the admissible routing paths to the destination. A scalable version of DAR, referred to as SDAR, is also proposed for minimizing the overheads associated with DAR in large network topologies. We show that DAR outperforms local adaptive routing by up to 79% and RCA by up to 58% in terms of latency on SPLASH-2 benchmarks. DAR and SDAR also outperform existing adaptive and oblivious routing algorithms in latency and throughput under synthetic traffic patterns on 8×8 and 16times;16 mesh topologies, respectively.

Priority queues are essential building blocks for implementing advanced per-flow service disciplines and hierarchical quality-of-service at high-speed network links. Scalable priority queue implementation requires solutions to two fundamental problems. The first is to sort queue elements in real time at ever increasing line speeds (e.g., at OC-768 rates). The second is to store a huge number of packets (e.g., millions of packets). In this paper, we propose novel solutions by decomposing the problem into two parts, a succinct priority index (PI) in SRAM that can efficiently maintain a real-time sorting of priorities, coupled with a DRAM-based implementation of large packet buffers. In particular, we propose three related novel succinct PI data structures for implementing high-speed PIs: a PI, a counting priority index (CPI), and a pipelined counting priority index (pCPI). We show that all three structures can be very compactly implemented in SRAM using only ⊖(U) space, where U is the size of the universe required to implement the priority keys (time stamps). We also show that our proposed PI structures can be implemented very efficiently as well by leveraging hardware-optimized instructions that are readily available in modern 64-bit processors. The operations on the PI and CPI structures take ⊖(logWU) time complexity, where W is the processor word length (i.e., W = 64). Alternatively, operations on the pCPI structure take amortized constant time with only ⊖(logWU) pipeline stages (e.g., only four pipeline stages for U = 16 million). Finally, we show the application of our proposed PI structures for the scalable management of large packet buffers at line speeds. The pCPI structure can be implemented efficiently in high-performance network processing applications such as advanced per-flow scheduling with quality-of-service guarantee.

Statistics counters are essential in network measurement on tracking various network statistics and implementing various network counting sketches. For such applications it is crucial to maintain a large number of statistics counters at very high speeds. On the Internet with millions of flows, potentially millions of counters are required to be updated at wirespeed of 40 Gb/s and beyond. It is widely accepted that SRAM is too costly to store such large counter arrays entirely, and DRAM is too slow to catch up with the line rate. In this paper, we propose a DRAM-based architecture that takes advantage of the performance of modern commodity DRAM by interleaving counter updates to multiple memory banks. Our architecture is based on the observation that most flows on the Internet consist of multiple packets that are transmitted during a relatively short period of time, which are referred to as traffic bursts. Our proposed architecture makes use of a simple randomization scheme and a set of small fully associative request queues to statistically guarantee a near-perfect load balancing of counter updates to the memory banks. The architecture explores the benefit of traffic bursts to greatly reduce the maximum size of the request queues while providing a diminishing overflow probability guarantee. We also develop queuing models to show that as long as the flow sizes are heavy-tailed distributed due to traffic bursts, the maximum request queue length is always bounded by a small constant. The simulation results confirm the effectiveness of our queuing models. The proposed statistics counter arrays can effectively maintain line rate updates to a large number of counters while guaranteeing a diminishing overflow probability in the system.

Networks-on-Chip (NoCs) are scalable fabrics for interconnection networks used in many-core architectures. ORION2.0 is a widely adopted NoC power and area estimation tool; however, its models for area, power and gate count can have large errors (up to 110% on average) versus actual implementation. In this work, we propose a new methodology that analyzes netlists of NoC routers that have been placed and routed by commercial tools, and then performs explicit modeling of control and data paths followed by regression analysis to create highly accurate gate count, area and power models for NoCs. When compared with actual implementations, our new models have average estimation errors of no more than 9.8% across microarchitecture and implementation parameters. We further describe modeling extensions that enable more detailed flit-level power estimation when integrated with simulation tools such as GARNET.

1/2 network capacity is often believed to be the limit of worst-case throughput for mesh networks. However, this paper provides a new worst-case throughput bound, which is higher than 1/2 network capacity, for odd radix two-dimensional mesh networks. In addition, we propose a routing algorithm called U2TURN that can achieve this worst-case throughput bound for odd radix meshes. For even radix meshes, we prove that U2TURN achieves the optimal worst-case throughput, namely, half of network capacity. U2TURN considers all routing paths with at most 2 turns and distributes the traffic loads uniformly in both X and Y dimensions. Theoretical analysis and simulation results show that U2TURN outperforms existing routing algorithms in worst-case throughput. Moreover, U2TURN achieves good average-throughput at the expense of approximately 1.5× minimal average hop count. For asymmetric meshes, we further propose an algorithm called “U2TURN-A” and provide theoretical analysis for different algorithms. Both theoretical analysis and simulation show that U2TURN and U2TURN-A outperform existing algorithms VAL, DOR and O1TURN in both worst-case and average throughput for asymmetric meshes.

Network-wide traffic measurement is important for various network management tasks, ranging from traffic accounting, traffic engineering, and network troubleshooting to security. Existing techniques for traffic measurement tend to be sub-optimal due to poor choice of monitor deployment location or due to constantly evolving monitoring objectives and traffic characteristics. It is not feasible to dynamically reconfigure/redeploy monitoring infrastructure to satisfy such evolving measurement requirements. In this paper, we present a distributed measurement-aware traffic engineering protocol based on a game-theoretic re-routing policy that attempts to optimally utilize existing monitor locations for maximizing the traffic measurement gain while ensuring that the traffic load distribution across the network satisfies some traffic engineering constraint. We introduce a novel cost function on each link that reflects both the measurement gain and the traffic engineering (TE) constraint. Individual routers compete with each other (in a game) to minimize their own costs for the downstream paths, i.e., each router dynamically gathers its cost information for upstream routers and use it to locally decide how to adjust traffic split ratios for each destination to the next-hop routers among these multiple equal-cost paths. Our routing policy guarantees not only a provable Nash equilibrium, but also a quick convergence without significant oscillations to an equilibrium state in which the measurement gain of the network is close to the best case performance bounds We evaluate the protocol via simulations using real traces/topologies (Abilene, AS6461 and GEANT). The simulation results show fast convergence (as expected from the theoretical results), improved measurement gains (e.g., 12 % higher) and much lower TE-violations (e.g., up to 100X smaller) compared to static, centralized measurement-aware routing framework in dynamic traffic scenario.

Many network processing applications require wirespeed access to large data structures or a large amount of packet and flow-level data. Therefore, it is essential for the memory system of a router to be able to support both read and write accesses to such data at link speeds. As link speeds continue to increase, router designers are constantly grappling with the unfortunate trade-offs between the speed and cost of SRAM and DRAM. The capacity of SRAMs is woefully inadequate in many cases and it proves too costly to store large data structures entirely in SRAM, while DRAM is viewed as too slow for providing wirespeed updates at such high speed. In this paper, we analyze a robust pipelined memory architecture that can emulate an ideal SRAM by guaranteeing with very high probability that the output sequence produced by the pipelined memory architecture is the same as the one produced by an ideal SRAM under the same sequence of memory read and write operations, except time shifted by a fixed pipeline delay of \Delta. Given a fixed pipeline delay abstraction, no interrupt mechanism is required to indicate when read data are ready or a write operation has completed, which greatly simplifies the use of the proposed solution. The design is based on the interleaving of DRAM banks together with the use of a reservation table that serves in part as a data cache. In contrast to prior interleaved memory solutions, our design is robust under all memory access patterns, including adversarial ones, which we demonstrate through a rigorous worst case theoretical analysis using a combination of convex ordering and large deviation theory.

Network-wide traffic measurement is important for various network management tasks, ranging from traffic accounting, traffic engineering, network troubleshooting to security. Previous research in this area has focused on either deriving better monitor placement strategies for fixed routing, or strategically routing traffic sub-populations over existing deployed monitors to maximize the measurement gain. However, neither of them alone suffices in real scenarios, since not only the number of deployed monitors is limited, but also the traffic characteristics and measurement objectives are constantly changing. This paper presents an MMPR (Measurement-aware Monitor Placement and Routing) framework that jointly optimizes monitor placement and dynamic routing strategy to achieve maximum measurement utility. The main challenge in solving MMPR is to decouple the relevant decision variables and adhere to the intra-domain traffic engineering constraints. We formulate it as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. Through experiments using real traces and topologies (Abilene , AS6461 , and GEANT ), we show that our heuristic solutions can achieve measurement gains that are quite close to the optimal solutions, while reducing the computation times by a factor of 23X in Abilene (small), 246X in AS6461 (medium), and 233X in GEANT (large), respectively.

The problem of efficiently maintaining a large number (say millions) of statistics counters that need to be updated at very high speeds (e.g., 40 Gb/s) has received considerable research attention in recent years. This problem arises in a variety of router management and data streaming applications where large arrays of counters are used to track various network statistics and implement various counting sketches. It proves too costly to store such large counter arrays entirely in SRAM, while DRAM is viewed as too slow for providing wirespeed updates at such high line rates. In particular, we propose a DRAM-based counter architecture that can effectively maintain wirespeed updates to large counter arrays. The proposed approach is based on the observation that modern commodity DRAM architectures, driven by aggressive performance roadmaps for consumer applications, such as video games, have advanced architecture features that can be exploited to make a DRAM-based solution practical. In particular, we propose a randomized DRAM architecture that can harness the performance of modern commodity DRAM offerings by interleaving counter updates to multiple memory banks. The proposed architecture makes use of a simple randomization scheme, a small cache, and small request queues to statistically guarantee a near-perfect load-balancing of counter updates to the DRAM banks. The statistical guarantee of the proposed randomized scheme is proven using a novel combination of convex ordering and large deviation theory. Our proposed counter scheme can support arbitrary increments and decrements at wirespeed, and they can support different number representations, including both integer and floating point number representations.

The increasing viability of 3-D silicon integration technology has opened new opportunities for chip architecture innovations. One direction is in the extension of 2-D mesh-based tiled chip-multiprocessor architectures into three dimensions. This paper focuses on efficient routing algorithms for such 3-D mesh networks. Existing routing algorithms suffer from either poor worst-case throughput (DOR, ROMM) or poor latency (VAL). Although the minimal routing algorithm O1TURN proposed in already achieves near-optimal worst-case throughput for 2-D mesh networks, the optimality result does not extend to higher dimensions. For 3-D and higher dimensional meshes, the worst-case throughput of O1TURN degrades tremendously. The main contribution of this paper is a new oblivious routing algorithm for 3-D mesh networks called randomized partially-minimal (RPM) routing. RPM provably achieves optimal worst-case throughput for 3-D meshes when the network radix is even and within a factor of 1/k2of optimal worst-case throughput when is odd. Finally, whereas VAL achieves optimal worst-case throughput at a penalty factor of 2 in average latency over DOR, RPM achieves (near) optimal worst-case throughput with a much smaller factor of 1.33. For practical asymmetric 3-D mesh configurations where the number of device layers are fewer than the number of tiles along the edge of a layer, the average latency of RPM reduces to just a factor of 1.11 to 1.19 of DOR. Additionally, a variant of RPM called randomized minimal first (RMF) routing is proposed, which leverages the inherent load-balancing properties of the network traffic to further reduce packet latency without compromising throughput.

Network-wide traffic measurement is of interest to network operators to uncover global network behavior for the management tasks of traffic accounting, debugging or troubleshooting, security, and traffic engineering. Increasingly, sophisticated network measurement tasks such as anomaly detection and security forensic analysis are requiring in-depth fine-grained flow-level measurements. However, performing in-depth per-flow measurements (e.g., detailed payload analysis) is often an expensive process. Given the fast-changing Internet traffic landscape and large traffic volume, a single monitor is not capable of accomplishing the measurement tasks for all applications of interest due to its resource constraint. Moreover, uncovering global network behavior requires network-wide traffic measurements at multiple monitors across the network since traffic measured at any single monitor only provides a partial view and may not be sufficient or accurate. These factors call for coordinated measurements among multiple distributed monitors. In this paper, we present a centralized optimization framework, LEISURE (Load-EqualIzed measurement), for load-balancing network measurement workloads across distributed monitors. Specifically, we consider various load-balancing problems under different objectives and study their extensions to support different deployment scenarios. We evaluate LEISURE via detailed simulations on Abilene and GEANT network traces to show that LEISURE can achieve much better load-balanced performance (e.g., 4.75X smaller peak workload and 70X smaller variance in workloads) across all coordinated monitors in comparison to naive solution (uniform assignment) to accomplish network-wide traffic measurement tasks.

For communications and networking channels, coding techniques are widely used to correct errors in corrupted messages. The "Quality of Protection" (QoP) that can be provided via error correction directly affects the "Quality of Service" (QoS) experienced by users. The errors are commonly assumed to be substitution or erasure errors. Such systems rely on perfect synchronization so that no bit is deleted and no extra bit is inserted. However, in a system without the presence of perfect synchronization, special coding algorithms may be required to correct potential insertion or deletion errors in transmitted messages. Especially for systems suffering from frequent loss of synchronization, packets may require many retransmissions to guarantee reliable communication. Such schemes may become too expensive to be practical. In this paper, we propose a new synchronization channel error model based on the observations from current communication systems. In this model, the channel introduces at most t synchronization errors in each run of the transmitted sequence. We present run-length limited permutation codes capable of correcting synchronization errors based on this channel error model. Compared to previously developed codes, our codes have the advantage of correcting frequent synchronization errors, and therefore they are suitable for disruptive network channels that suffer severe synchronization failures.

Router microarchitecture plays a central role in the performance of networks-on-chip (NoCs). Buffers are needed in routers to house incoming flits that cannot be immediately forwarded due to contention. This buffering can be done at the inputs or the outputs of a router, corresponding to an input-buffered router (IBR) or an output-buffered router (OBR). OBRs are attractive because they can sustain higher throughputs and have lower queuing delays under high loads than IBRs. However, a direct implementation of an OBR requires a router speedup equal to the number of ports, making such a design prohibitive under aggressive clocking needs and limited power budgets of most NoC applications. In this paper, a new router design based on a distributed shared-buffer (DSB) architecture is proposed that aims to practically emulate an OBR. The proposed architecture introduces innovations to address the unique constraints of NoCs, including efficient pipelining and novel flow control. Practical DSB configurations are also presented with reduced power overheads while exhibiting negligible performance degradation. Compared to a state-of-the-art pipelined IBR, the proposed DSB router achieves up to 19% higher throughput on synthetic traffic and reduces packet latency on average by 61% when running SPLASH-2 benchmarks with high contention. On average, the saturation throughput of DSB routers is within 7% of the theoretically ideal saturation throughput under the synthetic workloads evaluated.

In this paper, we present an exact active statistics counter architecture called Bucketized Rank Indexed Counters (BRICK) that can efficiently store per-flow variable-width statistics counters entirely in SRAM while supporting both fast updates and lookups (e.g., 40-Gb/s line rates). BRICK exploits statistical multiplexing by randomly bundling counters into small fixed-size buckets and supports dynamic sizing of counters by employing an innovative indexing scheme called rank indexing. Experiments with Internet traces show that our solution can indeed maintain large arrays of exact active statistics counters with moderate amounts of SRAM.

The choice of routing algorithm plays a vital role in the performance of on-chip interconnection networks. Adaptive routing is appealing because it offers better latency and throughput than oblivious routing, especially under non-uniform and bursty traffic. The performance of an adaptive routing algorithm is determined by its ability to accurately estimate congestion in the network. In this regard, maintaining global congestion information using a separate monitoring network offers better congestion visibility into distant parts of the network than solutions relying only on local congestion state. However, the main challenge in designing such routing schemes is to keep the logic and bandwidth overhead as low as possible to fit into the tight power, area and delay budgets of on-chip routers. In this paper, we propose a minimal destination-based adaptive routing strategy (DAR) where every node estimates the delay to every other node in the network, and routing decisions are based on these per-destination delay estimates. DAR outperforms Regional Congestion Awareness (RCA) [7], the best previously known adaptive routing algorithm that uses non-local congestion knowledge. This is because the per-destination delay estimates in DAR are more accurate and not corrupted by congestion on links outside the admissible routing paths to the destination. We show that DAR outperforms minimal adaptive routing by up to 65% and RCA by up to 41% in terms of latency on SPLASH-2 benchmarks. It also outperforms these algorithms in latency and throughput under synthetic traffic patterns on both 8x8 and 16x16 mesh topologies.

Over the course of this decade, uniprocessor chips have given way to multi-core chips which have become the primary building blocks of today's computer systems. The presence of multiple cores on a chip shifts the focus from computation to communication as a key bottleneck to achieving performance improvements. As industry moves towards many-core chips, networks-on-chip (NoCs) are emerging as the scalable fabric for interconnecting the cores. With power now the first-order design constraint, early-stage estimation of NoC power has become crucially important. Existing power models (e.g., ORION 2.0 [12], Xpipes [7], etc.) are based on certain router microarchitecture and circuit implementation. Therefore, when validated against different NoC prototypes - different router implementations - we saw significant deviation (up to 40% on average) that can lead to erroneous NoC design choices. This has prompted our development of a new, accurate architecture- and circuit implementation-independent router power and area modeling methodology with complete portability across existing NoC component libraries. Also, validation against a range of implemented router designs confirms substantial improvement in accuracy over existing models.

Networks-on-chip (NoCs) are becoming increasingly important in general-purpose and application-specific multi-core designs. Although uniform router configurations are appropriate for generalpurpose NoCs, router configurations for application-specific NoCs can be non-uniformly optimized to application-specific traffic characteristics. In this paper, we specifically consider the problem of virtual channel (VC) allocation in application-specific NoCs. Prior solutions to this problem have been average-rate driven. However, average-rate models are poor representations of real application traffic, and can lead to designs that are poorly matched to the application. We propose an alternate trace-driven paradigm in which configuration of NoCs is driven by application traces. We propose two simple greedy trace-driven VC allocation schemes. Compared to uniform allocation, we observe up to 51 % reduction in the number of VCs under a given average packet latency constraint, or up to 74 % reduction in average packet latency with same number of VCs. Our results suggest that average-rate driven methods cannot effectively select appropriate links for VC allocation because they fail to consider the impact of traffic bursts. As a case study, we compare our proposed approach with an existing average-rate driven method [9] and observe up to 35 % reduction in the number of VCs for a given target latency. 1.

Routers need to store temporarily a large number of packets in response to congestion. DRAM is typically needed to implement large packet buffers, but DRAM devices have worst-case random access latencies that are too slow to match the bandwidth requirements of high-performance routers. Existing DRAM-based architectures for supporting linespeed queue operations can be classified into three categories: prefetching-based, randomization-based, and reservation-based. They are all based on interleaving memory accesses across multiple parallel DRAM banks for achieving higher memory bandwidths, but they differ in their packet placement and memory operation scheduling mechanisms. In this paper, we present an efficient reservation-based packet buffer architecture based on the concept of blocks. The proposed block-based solution achieves an order of magnitude reduction in the total SRAM size. It is scalable to growing packet storage requirements in routers while matching increasing line rates.

As industry moves towards many-core chips, networks-on-chip (NoCs) are emerging as a scalable communication fabric for interconnecting the cores. With increasing core counts, there is a corresponding increase in communication demands in multi-core designs to facilitate high core utilization, and a consequent critical need for high-performance NoCs. Another megatrend in advanced technologies is that power has become the most critical design constraint. In this paper, we focus on trace-driven virtual channel (VC) allocation in application-specific NoCs. We propose a new significant VC failure metric to capture the impact of VCs on network performance and efficiently drive NoC optimization. Our proposed metaheuristics achieve up to 38% reduction in the number of VCs under a given average packet latency constraint. In addition, compared to a recently proposed trace-driven VC allocation approach, we obtain up to an O(|L|) speedup, where |L| is total number of links in the network, with no degradation in the quality of results.

Many network processing applications require wirespeed access to large data structures or a large amount of flow-level data, but the capacity of SRAMs is woefully inadequate in many cases. In this paper, we analyze a robust pipelined memory architecture that can emulate an ideal SRAM by guaranteeing with very high probability that the output sequence produced by the pipelined memory architecture is the same as the one produced by an ideal SRAM under the same sequence of memory read and write operations, except time-shifted by a fixed pipeline delay of Δ. The design is based on the interleaving of DRAM banks together with the use of a reservation table that serves in part as a data cache. In contrast to prior interleaved memory solutions, our design is robust even under adversarial memory access patterns, which we demonstrate through a rigorous worst-case theoretical analysis using a combination of convex ordering and large deviation theory.

Router microarchitecture plays a central role in the performance of an on-chip network (NoC). Buffers are needed in routers to house incoming flits which cannot be immediately forwarded due to contention. This buffering can be done at the inputs or the outputs of a router, corresponding to an input-buffered router (IBR) or an output-buffered router (OBR). OBRs are attractive because they can sustain higher throughputs and have lower queuing delays under high loads than IBRs. However, a direct implementation of an OBR requires a router speedup equal to the number of ports, making such a design prohibitive under aggressive clocking needs and limited power budgets of most NoC applications. In this paper, we propose a new router design that aims to emulate an OBR practically, based on a distributed shared-buffer (DSB) router architecture. We introduce innovations to address the unique constraints of NoCs, including efficient pipelining and novel flow-control. We also present practical DSB configurations that can reduce the power overhead with negligible degradation in performance. The proposed DSB router achieves up to 19% higher throughput on synthetic traffic and reduces packet latency by 60% on average for SPLASH-2 benchmarks with high contention, compared to a state-of-art pipelined IBR. On average, the saturation throughput of DSB routers is within 10% of the theoretically ideal saturation throughput under the synthetic workloads evaluated.

A Shrew attack, which uses a low-rate burst carefully designed to exploit TCP's retransmission timeout mechanism, can throttle the bandwidth of a TCP flow in a stealthy manner. While such an attack can significantly degrade the performance of all TCP-based protocols and services including Internet routing (e.g., BGP), no existing scheme clearly solves the problem in real network scenarios. In this paper, we propose a simple protection mechanism, called SAP (Shrew Attack Protection), for defending against a Shrew attack. Rather than attempting to track and isolate Shrew attackers, SAP identifies TCP victims by monitoring their drop rates and preferentially admits those packets from the victims with high drop rates to the output queue. This is to ensure that well-behaved TCP sessions can retain their bandwidth shares. Our simulation results indicate that under a Shrew attack, SAP can prevent TCP sessions from closing, and effectively enable TCP flows to maintain high throughput. SAP is a destination-port-based mechanism and requires only a small number of counters to find potential victims, which makes SAP readily implementable on top of existing router mechanisms.

Network operators need high-capacity router architectures that can offer scalability, provide throughput guarantees, and maintain packet ordering. However, current centralized crossbar-based architectures cannot scale to fast line rates and high port counts. On the other hand, while load-balanced switch architectures that rely on two identical stages of fixed configuration meshes appear to be an effective way to scale Internet routers to very high capacities, they incur a large worst-case packet reordering that is at best quadratic to the switch size. In this paper, we introduce the concurrent matching switch (CMS) architecture, which also uses two identical stages of fixed configuration meshes with the same scalability properties as current load-balanced routers. However, by adopting a novel contention-resolution architecture that is scalable and distributed, the CMS architecture enforces packet ordering throughout the switch. Using the CMS architecture, we show that scalability, 100% throughput, packet ordering, andO(1) amortized time complexity with sequential hardware per linecard can all be achieved. We further demonstrate a delay analysis for the CMS architecture.

Torus, mesh, and flattened butterfly networks have all been considered as candidate architectures for on-chip interconnection networks. In this paper, we study the problem of optimal oblivious routing for one of these architecture classes, namely, the torus network. We introduce a new closed-form oblivious routing algorithm called W2TURN that is worst-case throughput optimal for 2D-torus networks. W2TURN is based on a weighted random selection of paths that contain at most two turns. Restricting the maximum number of turns in routing paths to just two results in a simple deadlock-free implementation of W2TURN. In terms of average hop count, W2TURN outperforms the best previously known closed-form worst-case throughput optimal routing algorithm called IVAL [14]. We also provide another routing algorithm based on the weighted random selection of paths with at most two turns called I2TURN and show that it is equivalent to IVAL. However, I2TURN eliminates the need for loop removal at runtime and provides a closed-form analytical expression for evaluating the average hop count. The latter enables us to demonstrate analytically that W2TURN strictly outperforms IVAL (and I2TURN) in average hop count. Finally, we present a new optimal weighted random routing algorithm for rings called WRD (Weighted Random Direction). WRD provides a closed form expression for the the optimal distribution of traffic along the minimal and non-minimal directions in a ring topology to achieve minimum average hop count under maximum worst-case throughput.

Recently, a near-optimal oblivious routing algorithm for 3D mesh networks called Randomized Partially-Minimal (RPM) routing was proposed [12], which works by load-balancing traffic across vertical layers and routing minimally on each horizontal layer. It achieves optimal worst-case throughput when the network radix k is even and within a factor of 1/k2 of optimal when k is odd, and it achieves significantly lower latencies than Valiant routing [18], the best previously known optimal worst-case throughput algorithm. This paper presents a novel layer-multiplexed (LM) architecture for 3D on-chip networks that exploits the optimality of RPM together with the short inter-layer wiring delays enabled in 3D technology. The LM architecture replaces the one-layer-per-hop routing in a 3D mesh with simpler vertical demultiplexing and multiplexing structures. The proposed LM architecture can achieve the same worst-case throughput as a 3D mesh by adapting RPM routing to the LM architecture. However, the LM architecture consumes 27% less power, occupies 27% less area, attains 14.5% higher average throughput, and achieves 33% lower worst-case hop count for a symmetric 4x4x4 mesh topology. On an asymmetric 8 x 8 x 4 mesh, the LM architecture achieves comparable average-case throughput to a 3D mesh, but consumes 26% less power, takes up 27% less area and attains 20% lower worst-case hop count.

DRAM is typically needed to implement large packet buffers, but DRAM devices have worst-case random access latencies that are too slow to match the bandwidth requirements of high-performance routers. Existing DRAM-based

The problem of maintaining efficiently a large number (say millions) of statistics counters that need to be updated at very high speeds (e.g. 40 Gb/s) has received considerable research attention in recent years. This problem arises in a variety of router management and data streaming applications where large arrays of counters are used to track various network statistics and implement various counting sketches. It proves too costly to store such large counter arrays entirely in SRAM while DRAM is viewed as too slow for providing wirespeed updates at such high speeds.

A Shrew attack, which uses a low-rate burst carefully designed to exploit TCP's retransmission timeout mechanism, can throttle the bandwidth of a TCP flow in a stealthy manner. While such an attack can significantly degrade the performance of all TCP-based protocols and services including Internet routing (e.g., BGP), no existing scheme clearly solves the problem in real network scenarios. In this paper, we propose a simple protection mechanism, called SAP (Shrew Attack Protection), for defending against a Shrew attack. Rather than attempting to track and isolate Shrew attackers, SAP identifies TCP victims by monitoring their drop rates and preferentially admits those packets from victims with high drop rates to the output queue. This is to ensure that well-behaved TCP sessions can retain their bandwidth shares. Our simulations indicate that under a Shrew attack, SAP can prevent TCP sessions from closing, and effectively enable TCP flows to maintain high throughput. SAP is a destination-port-based mechanism and requires only a small number of counters to find potential victims, which makes SAP readily implementable on top of existing router mechanisms.

An important goal of bandwidth allocation is to maximize the utilization of network resources while sharing the resources in a fair manner among network flows. To strike a balance between fairness and throughput, a widely studied criterion in the network community is the notion of max-min fairness. However, the majority of work on max-min fairness has been limited to the case where the routing of flows has already been defined and this routing is usually based on a single fixed routing path for each flow. In this paper, we consider the more general problem in which the routing of flows, possibly over multiple paths per flow, is an optimization parameter in the bandwidth allocation problem. Our goal is to determine a routing assignment for each flow so that the bandwidth allocation achieves optimal utility max-min fairness with respect to all feasible routings of flows. We present evaluations of our proposed multi-path utility max-min fair allocation algorithms on a statistical traffic engineering application to show that significantly higher minimum utility can be achieved when multi-path routing is considered simultaneously with bandwidth allocation under utility max-min fairness, and this higher minimum utility corresponds to significant application performance improvements.

Priority queues are an essential building block for implementing advanced per-flow service disciplines at high-speed network links. In this paper, we propose novel solutions to the scalable implementation of priority queues by decomposing the problem into two parts, a succinct priority index in SRAM that can efficiently maintain a real-time sorting of priorities, coupled with a DRAM-based implementation of large packet buffers. In particular, we propose three related novel succinct priority index data structures for implementing high-speed priority indexes: a Priority-Index (PI), a Counting-Priority-Index (CPI), and a Pipelined Counting-Priority-Index (Pipelined CPI). We show that all three structures can be very compactly implemented in SRAM using only Theta(U) space, where U is the size of the universe required to implement the priority keys (timestamps). We also show that our proposed priority index structures can be implemented very efficiently as well by leveraging hardware-optimized instructions that are readily available in modern 64-bit microprocessors. The operations on the PI and CPI structures take Theta(logWU) time, where W is the processor word-length (i.e., W = 64 bits). Alternatively, operations on the Pipelined CPI structure take constant time with only Theta(logWU) pipeline stages. Finally, we show the application of our proposed priority index structures for scalable management of large packet buffers at line speeds.

In this paper, we consider the problem of synthesizing custom networks-on-chip (NoC) architectures that are optimized for a given application. We consider both unicast and multicast traffic flows in the input specification. Multicast traffic flows are used in a variety of applications, and their direct support with only replication of packets at optimal bifurcation points rather than full end-to-end replication can significantly reduce network contention and resource requirements. Our problem formulation is based on the decomposition of the problem into the inter-related steps of finding good flow partitions, deriving a good physical network topology for each group in the partition, and providing an optimized network implementation for the derived topologies. Our solutions may be comprised of multiple custom networks, each interconnecting a subset of communicating modules. We propose several algorithms that can systematically examine different flow partitions, and we propose rectilinear-Steiner-tree (RST)-based algorithms for generating efficient network topologies. Our design flow integrates floorplanning, and our solutions consider deadlock-free routing. Experimental results on a variety of NoC benchmarks showed that our synthesis results can on average achieve a 4.82 times reduction in power consumption over different mesh implementations on unicast benchmarks and a 1.92 times reduction in power consumption on multicast benchmarks. Significant improvements in performance were also achieved, with an average of 2.92 times reduction in hop count on unicast benchmarks and 1.82 times reduction in hop count on multicast benchmarks. To further gauge the effectiveness of our heuristic algorithms, we also implemented an exact algorithm that enumerates all distinct set partitions. For the benchmarks where exact results could be obtained, our algorithms on average can achieve results within 3% of exact results, but with much shorter execution times.

In this paper, we present an exact active statistics counter architecture called BRICK (Bucketized Rank Indexed Counters) that can efficiently store per-flow variable-width statistics counters entirely in SRAM while supporting both fast updates and lookups (e.g., 40 Gb/s line rates). BRICK exploits statistical multiplexing by randomly bundling counters into small fixed-size buckets and supports dynamic sizing of counters by employing an innovative indexing scheme called rank-indexing. Experiments with Internet traces show that our solution can indeed maintain large arrays of exact active statistics counters with moderate amounts of SRAM.

This paper considers the problem of synthesizing application-specific Network-on-Chip (NoC) architectures. We propose two heuristic algorithms called CLUSTER and DECOMPOSE that can systematically examine different set partitions of communication flows, and we propose Rectilinear-Steiner-Tree (RST) based algorithms for generating an efficient network topology for each group in the partition. Different evaluation functions in fitting with the implementation backend and the corresponding implementation technology can be incorporated into our solution framework to evaluate the implementation cost of the set partitions and RST topologies generated. In particular, we experimented with an implementation cost model based on the power consumption parameters of a 70nm process technology where leakage power is a major source of energy consumption. Experimental results on a variety of NoC benchmarks showed that our synthesis results can on average achieve a 6.92 × reduction in power consumption over the best standard mesh implementation. To further gauge the effectiveness of our heuristic algorithms, we also implemented an exact algorithm that enumerates all distinct set partitions. For the benchmarks where exact results could be obtained, our CLUSTER and DECOMPOSE algorithms on average can achieve results within 1 % and 2 % of exact results, with execution times all under 1 second whereas the exact algorithms took as much as 4.5 hours.

The increasing viability of three dimensional (3D) silicon integration technology has opened new opportunities for chip architecture innovations. One direction is in the extension of two-dimensional (2D) mesh-based tiled chip-multiprocessor architectures into three dimensions. In this paper, we focus on efficient routing algorithms for such 3D mesh networks. As in the case of 2D mesh networks, throughput and latency are important design metrics for routing algorithms. Existing routing algorithms suffer from either poor worst-case throughput (DOR , ROMM) or poor latency (VAL). Although the minimal routing algorithm O1TURN proposed in already achieves near-optimal worst-case throughput for the 2D case, the optimality result does not extend to higher dimensions. For 3D and higher dimensional meshes, the worst-case throughput of O1TURN degrades tremendously. The main contribution of this paper is the design of a new oblivious routing algorithm for 3D mesh networks called randomized partially-minimal (RPM) routing. RPM provably achieves optimal worst-case throughput for 3D meshes when the network radix k is even and within a factor of 1/k2of optimal worst-case throughput when k is odd. RPM also outperforms VAL, DOR, ROMM, and O1TURN in average-case throughput by 33.3%, 111%, 47%, and 30%, respectively when averaged over one million random traffic patterns on an 8 times 8 times 8 topology. Finally, whereas VAL achieves optimal worst-case throughput at a penalty factor of 2 in average latency over DOR, RPM achieves (near) optimal worst-case throughput with a much smaller factor of 1.33. In practice, the average latency of RPM is expected to be closer to minimal routing because 3D mesh networks are not expected to be symmetric in 3D chip designs. The number of available device layers is expected to be much less than the number of processor tiles that can be placed along an edge of a device layer. For practical asymmetric 3D mesh configurations, the average latency of RPM reduces to just a factor of 1.11 of DOR.

The increasing viability of three dimensional (3D) silicon integration technology has opened new opportunities for chip design innovations, including the prospect of extending emerging systems-on-chip (SoC) design paradigms based on networks-on-chip (NoC) interconnection architectures to 3D chip designs. In this paper, we consider the problem of designing application-specific 3D-NoC architectures that are optimized for a given application. We present novel 3D-NoC synthesis algorithms that make use of accurate power and delay models for 3D wiring with through-silicon vias. In particular, we present a very efficient 3D-NoC synthesis algorithm called ripup-reroute-and-router-merging (RRRM), that is based on a rip-up and reroute formulation for routing flows and a router merging procedure for network optimization. Experimental results on 3D-NoC design cases show that our synthesis results can on average achieve a 74% reduction in power consumption and a 17% reduction in hop count over regular 3D mesh implementations and a 52% reduction in power consumption and a 17% reduction in hop count over optimized 3D mesh implementations.

Bloom filter and its variants have found widespread use in many networking applications. For these applications, minimizing storage cost is paramount as these filters often need to be implemented using scarce and costly (on-chip) SRAM. Besides supporting membership queries, Bloom filters have been generalized to support deletions and the encoding of information. Although a standard Bloom filter construction has proven to be extremely space-efficient, it is unnecessarily costly when generalized. Alternative constructions based on storing fingerprints in hash tables have been proposed that offer the same functionality as some Bloom filter variants, but using less space. In this paper, we propose a new fingerprint hash table construction called Rank-Indexed Hashing that can achieve very compact representations. A rank-indexed hashing construction that offers the same functionality as a counting Bloom filter can be achieved with a factor of three or more in space savings even for a false positive probability of just 1%. Even for a basic Bloom filter function that only supports membership queries, a rank-indexed hashing construction requires less space for a false positive probability as high as 0.1%, which is significant since a standard Bloom filter construction is widely regarded as extremely space-efficient for approximate membership problems.

Network operators need high-capacity router architectures that can offer scalability, provide throughput and performance guarantees, and maintain packet ordering. However, previous router architectures based on centralized crossbar-based architectures cannot scale to fast line rates and high port counts. Recently, a new scalable router architecture called the Concurrent Matching Switch (CMS)[5]was introduced that offers scalability by utilizing a fully distributed architecture based on two identical stages of fixed configuration meshes. It has been shown that fixed configuration meshes can be scaled to very fast line rates and highport counts via optical implementations.It has also been shown that the CMS architecture can achieve 100% through-put and packet ordering with only sequential hardware and O (1) amortized time complexity operations at each linecard. However, no delay performance guarantees have been shown for CMS.

Priority queues are essential for various network processing applications, including per-flow queueing with quality-of-service (QoS) guarantees, management of large fast packet buffers, and management of statistics counters. In this paper, we propose a new data structure for implementing high-performance priority queues based on a pipelined version of the van Emde Boas tree. We show that we can achieve O(1) amortized time operations using our architecture, but we can achieve this algorithmic efficiency using only O (log log u) number of pipelined stages, where u is the size of the universe used to represent the priority keys.

This paper investigates the mapping of stream programs to wide-issue clustered VLIW processors so that designers can leverage their existing investments in VLIW-based platforms to harness the advantages of stream programming.

Priority queues are often used in many network processing applications. Applications include sophisticated per-flow scheduling for providing advanced quality-of-service (QoS) guarantees, fast packet buffer memory management, and exact maintenance of statistics counters for real-time network measurements. In all these applications, the priority queues used must operate at very high-speeds, e.g. at 40 Gbps rates and beyond. One widely used data structure for implementing priority queues is the heap data structure. However, the logarithmic time complexity of heap operations is often too slow for increasingly fast line rates. To achieve constant time complexity, the pipelined heap structure has been proposed. In this paper, we describe new architecture techniques for the efficient implementation of pipelined heaps. In particular, we focus on aggressive memory management and pipelining techniques.

Network operators need high-capacity router architectures that can offer scalability, provide throughput guarantees, and maintain packet ordering. However, current centralized crossbar-based architectures cannot scale to fast line rates and high port counts. On the other hand, while load-balanced switch architectures that rely on two identical stages of fixed configuration meshes appear to be an effective way to scale Internet routers to very high capacities, they incur a large worst-case packet reordering that is at best quadratic to the switch size. In this paper, we introduce the concurrent matching switch (CMS) architecture, which also uses two identical stages of fixed configuration meshes with the same scalability properties as current load-balanced routers. However, by adopting a novel contention-resolution architecture that is scalable and distributed, the CMS architecture enforces packet ordering throughout the switch. Using the CMS architecture, we show that scalability, 100% throughput, packet ordering, and O(1) amortized time complexity with sequential hardware per linecard can all be achieved. We further demonstrate a delay analysis for the CMS architecture.

For monitoring and measuring high-speed networks accurately in real-time, a large number of statistics counters may need to be maintained at wirespeeds (e.g. 10 Gbit/s), Expensive, but fast. SRAM is needed for storing the counters to satisfy the speed requirements. However, high-density, but slower, DRAM is needed to provide the necessary storage capacity for storing all counter values exactly. Recent papers by Shah et al. (2003) and Ramabhadran and Varghese (2003) have addressed the problem using counter memory architectures based on one level of fast SRAM for storing partial counter values and a high-capacity DRAM for storing full counter values. In this paper, we propose to extend their work with a multi-level counter memory architecture to reduce the amount of fast memory required. Our multi-level counter memory architecture can reduce the amount of equivalent fast memory storage required by as much as 28%.

We present a new input-queued switch architecture designed to support deadline-ordered scheduling at extremely high-speeds. In particular, deadline-ordered scheduling is enabled through a combination of hardware-based sorted priority queues called P-heaps and a round-robin crossbar scheduler. The priority queues are implemented using a novel scalable pipelined heap-based architecture. Using a 0.35 micron CMOS standard-cell technology, we demonstrate a 32-port switch capable of sustaining 10 Gb/s line rates.

In this paper, we present a fast and scalable pipelined priority queue architecture for use in high-performance switches with support for fine grained quality of service (QoS) guarantees. Priority queues are used to implement highest-priority-first scheduling policies. Our hardware architecture is based on a new data structure called a pipelined heap, or P-heap for short. This data structure enables the pipelining of the enqueue and dequeue operations, thereby allowing these operations to execute in essentially constant time. In addition to being very fast, the architecture also scales very well to a large number of priority levels and to large queue sizes. We give a detailed description of this new data structure, the associated algorithms and the corresponding hardware implementation. We have implemented this new architecture using a 0.35 micron CMOS technology. Our current implementation can support 10 Gb/s connections with over 4 billion priority levels.

Article Hardware compilation for FPGA-based configurable computing machines Share on Authors: Xiaohan Zhu University of California, San Diego University of California, San DiegoView Profile , Bill Lin University of California, San Diego University of California, San DiegoView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 697–702https://doi.org/10.1145/309847.310030Online:01 June 1999Publication History 6citation401DownloadsMetricsTotal Citations6Total Downloads401Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Crossbar architectures are widely used to implement high-performance network switches and routers. A crossbar switch can transfer cells between multiple ports simultaneously by closing multiple cross points. This crossbar configuration must be determined by an intelligent centralized scheduler that can ensure fairness and high utilization. In this paper, we describe the design and implementation of two symmetric scheduling algorithms for configuring crossbars in input-queued switches that support virtual output queueing. Our target is a fast packet switch that can support 32 ports, each operating at 20 Gbps. Using a 0.35 /spl mu/m CMOS process, the faster of the two schedulers is capable of configuring a 32/spl times/32 crossbar once every 12.61 ns. Our scheduler designs are based on a two-dimensional ripple carry arbiter architecture. To ensure fairness, both architectures support a round robin priority rotation scheme. Based on network simulations, we show that our arbiter designs can achieve near optimal system performance.

We describe a new compositional software synthesis method for synthesizing concurrent software programs into ordinary C programs so that they can be executed on embedded processors without the need for a run-time multitasking operating system. The synthesized C program can be readily retargeted to different processors using available optimizing C compilers. The method works by transforming the initial input specification into a set of interacting Petri net components. It then applies a quasi-static scheduling method on each Petri net component to produce a corresponding state machine model. The resulting set of interacting state machines are then mapped into a single C program, which can finally be compiled to native machine code via conventional C compilers. In the degenerate case, each process in the initial input specification is mapped into a separate Petri net component. In this case, the size of the resulting C program is directly proportional to the size of the original concurrent specification. Thus, this technique can scale well to large applications and is immune to code explosion.

We present a Petri net theoretic approach to the software synthesis problem that can synthesize ordinary C programs from process-based concurrent specifications without the need for a run-time multi-threading environment. The synthesized C programs can be readily retargeted to different processors using available optimizing C compilers. Our compiler can also generate sequential Java programs as output, which can also be readily mapped to a target processor without the need for a multi-threading environment. Initial results demonstrate significant potentials for improvements over current run-time solutions.

Currently, run-time operating systems are widely used to implement concurrent embedded applications. This run-time approach to multi-tasking and inter-process communication can introduce significant overhead to execution times and memory requirements-prohibitive in many cases for embedded applications where processor and memory resources are scarce. In this paper, we present a static compilation approach that generates ordinary C programs at compile-time that can be readily retargeted to different processors, without including or generating a run-time scheduler. Our method is based on a novel Petri net theoretic approach.

This paper presents a new formal method for the efficient verification of concurrent systems that are modeled using a safe Petri net representation. Our method generalizes upon partial-order methods to explore concurrently enabled conflicting paths simultaneously. We show that our method can achieve an exponential reduction in algorithmic complexity without resorting to an implicit enumeration approach.

We examine the implications of a new hazard-free combinational logic synthesis method, which generates multiplexor-based networks from binary decision diagrams (BDD's)-representations of logic functions factored recursively with respect to input variables-on extended burst-mode asynchronous synthesis. First, this method guarantees that there exists a hazard-free BDD-based implementation for every legal extended burst-mode specification. Second, it reduces the constraints on state minimization and assignment, which reduces the number of additional state variables required in many cases. Third, in cases where conditional signals are sampled, it eliminates the need for state variable changes preceding output changes, which reduces overall input-to-output latency. Last, we describe a circuit that exemplifies how the BDD variable ordering affects the path delay.

We describe a system design methodology well-suited for telecom network applications. This methodology is being developed into a compiler called Matisse. The entry point for this methodology is a system specification model that is first compiled into an abstract machine. The abstract machine is implementation-independent, which permits the exploration of different embedded hardware/software realizations. The proposed methodology and tools bridge the gap between system specification and synthesis tools commercially available. This yields several advantages over the design methodology currently used in industry.

We reflect on the nature of digital telecommunication systems. We argue that these systems require, by nature, a heterogeneous specification and an implementation with heterogeneous architectural styles. CoWare is a hardware/software co-design environment based on a data model that allows to specify, simulate, and synthesize heterogeneous hardware/software architectures from a heterogeneous specification. CoWare is based on the principle of encapsulation of existing hardware and software compilers and special attention is paid to the interactive synthesis of hardware/software and hardware/hardware interfaces. The principles of CoWare are illustrated by the design process of a spread-spectrum receiver for a pager system.

We present a new sum-of-product-based asynchronous architecture, called the N-SHOT architecture, that operates correctly under internal hazardous responses and guarantees hazard-freeness at the observable noninput signals. We formally prove that within this architecture, a very wide class of semimodular state graphs with input choices (either distributive or nondistributive) that satisfy the complete state coding property always admit a correct implementation, As with synchronous circuits, we permit internal hazards in the combinational logic core, which means that we can make use of conventional combinational logic minimization methods to produce the sum-of-product implementation. This represents a significant departure from most existing methods that require the combinational logic to be hazard-free and are mainly valid for distributive behaviors, We also present optimizations for this architecture which are related to state graph properties.

In this paper, we describe a system design methodology for the concurrent development of hybrid software/hardware systems for telecom network applications. This methodology is based on the results of an investigation and evaluation of an actual industrial system design application for ATM-based broad-band networks. The aim of this methodology is to provide an integrated design flow from system specification to implemen-tation. 1

Deep sub-micron processing technologies have enabled the implementation of new application-specificembeddedarchitecturesthat integrate multiple software programmable processors (e.g. DSPs, microcontrollers) and dedicated hardware components together onto a single cost-efficient IC. These application-specific architectures are emerging as a key design solution to today's microelectronics design problems, which are being driven by emerging applications in the areas of wireless communication, broadband networking, and multimedia computing. However, the constructionof these customized heterogeneous multiprocessor architectures, while ensuring that the hardware and software parts communicate correctly, is a tremendously difficult and highly error proned task with little or no tool support. In this paper, we present a solution to this embedded architecture cosynthesis problem based on an orchestrated combination of architectural strategies, parameterized libraries, and software tool support....

Heterogeneous embedded multiprocessor architectures are becoming more prominent as a key design solution to today's microelectronics design problems.These application-specific architectures integrate multiple software programmable processors and dedicated hardwarecomponents together on to a single cost-efficient IC.In contrast to general-purpose computer systems, embedded systems are designed and optimized to provide specific functionality, using possibly a combination of different classes of processors (e.g.DSPs, microcontrollers) from different vendors.While these customized heterogeneous multiprocessor architectures offer designers new possibilities to tradeoff programmability, processing performance, power dissipation, and design turnaround time, there is currently a lack of tools to support the programming of these architectures.In this paper, we consider the problem of providing real-time kernel support for managing the concurrent software tasks that are distributed over a set of processorsin an application-specific multiprocessorarchitecture.This is complementary to current research activities that aim to provide efficient retargetable code generation [8,11,10] for a broad range of embedded processors.

personal or class-room use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copying is

Many asynchronous designs are naturally specified and implemented hierarchically as an interconnection of separate asynchronous modules that operate concurrently and communicate with each other.This paper is concerned with the problem of synthesizing such hierarchically defined systems.When the individual components are synthesized and implemented separately, it is desirable to take into account the degrees of freedom that arise from the interactions with the other components and from the specification.Specifically, we consider how one can find the set of implementations that can be "correctly substituted" for a component in the system while preserving the behavior of the total system.The notion of correct substitution is formally defined for a hierarchical network of possibly non-deterministic modules and a new solution framework based on trace theory is presented to compute and represent this complete set of correct substitutions.We show that the complete set can be captured by a single trace structure using the notion of a "maximal trace structure".We indicate how asynchronous synthesis methods may be applied to explore the solution space e.g. to generate a delay-insensitive implementation.

We present a new sum-of-product based asynchronous architecture, called the N-SHOT architecture, that operates correctly under internal hazardous responses and guarantees hazard-freeness at the observable non-input signals.We formally prove that within this architecture a very wide class of semi-modular state graphs with input choices (either distributive or non-distributive) that satisfy the complete state coding property always admit a correct implementation.As with synchronous circuits, we permit internal hazards in the combinational logic core, which means we can make use of conventional combinational logic minimization methods to produce the sum-of-product implementation.This represents a significant departure from most existing methods that require the combinational logic to be hazard-free and are mainly valid for distributive behaviors.

This paper presents an automated method for the synthesis of multiple-input-change (MIC) asynchronous state machines. Asynchronous state machine design is subtle since, unlike synchronous synthesis, logic must be implemented without hazards, and state codes must be chosen carefully to avoid critical races. We formulate and solve an optimal hazard-free and critical race-free encoding problem for a class of MIC asynchronous state machines called burst-mode. Analogous to a paradigm successfully used for the optimal encoding of synchronous machines, the problem is formulated as an input encoding problem. Implementations are targeted to sum-of-product realizations. We believe this is the first general method for the optimal encoding of hazard-free MIC asynchronous state machines under a generalized fundamental mode of operation. Results indicate that improved solutions are produced, ranging up to 17% improvement.

Telecommunication network management applications often require application-specific ICs that use large dynamically allocated stored data structures. Currently available hardware synthesis environments typically do not support dynamic data structure concepts and their associated memory synthesis problems. In this paper we address the background memory management task in a hardware design trajectory, which includes allocation of a distributed memory architecture, assignment and mapping of abstract data structures to memories, and synthesis of dynamic management behavior. With this approach to explore for the optimal memory architecture, the design entry point is lifted to a higher level than currently used for behavioral synthesis, as the specification can be a high-level program using data abstraction. The power of our approach will be substantiated on an industrial high-performance telecommunication ASIC design.

This paper presents a new efficient state assignment framework for synthesizing asynchronous state graphs. This framework operates purely at the state graph level and is applicable to a broad class of behaviors. In this paper we focus the framework for solving the complete state coding problem. This method has been automated and applied to a large set of asynchronous circuits. It achieves significant improvements in terms of both circuit area and computation time.

We describe a new method for directly synthesizing a hazard-free multilevel logic implementation from a given logic specification. The method is based on free/ordered Binary Decision Diagrams (BDD's), and is naturally applicable to multiple-output logic functions. Given an incompletely-specified (multiple-output) Boolean function, the method produces a multilevel logic network that is hazard-free for a specified set of multiple-input changes. We assume an arbitrary (unbounded) gate and wire delay model under a pure delay (PD) assumption, we permit multiple-input changes, and we consider both static and dynamic hazards under the fundamental-mode assumption. Our framework is thus general and powerful. While it is not always possible to generate hazard-free implementations using our technique, we show that in some cases hazard-free multilevel implementations can be generated when hazard-free two-level representations cannot be found. This problem is generally regarded as a difficult problem and it has important applications in the field of asynchronous design. The method has been automated and applied to a number of examples.>

Recently developed methods for power estimation have primarily focused on combinational logic. We present a framework for the efficient and accurate estimation of average power dissipation in sequential circuits. Switching activity is the primary cause of power dissipation in CMOS circuits. Accurate switching activity estimation for sequential circuits is considerably more difficult than that for combinational circuits, because the probability of the circuit being in each of its possible states has to be calculated. The Chapman-Kolmogorov equations can be used to compute the exact state probabilities in steady state. However, this method requires the solution of a linear system of equations of size 2/sup N/ where N is the number of flip-flops in the machine. We describe a comprehensive framework for exact and approximate switching activity estimation in a sequential circuit. The basic computation step is the solution of a nonlinear system of equations which is derived directly from a logic realization of the sequential machine. Increasing the number of variables or the number of equations in the system results in increased accuracy. For a wide variety of examples, we show that the approximation scheme is within 1-3% of the exact method, but is orders of magnitude faster for large circuits. Previous sequential switching activity estimation methods can have significantly greater inaccuracies.>

Abstract Current asynchronous tools are focussed mainly on the design of a single interface module. In many applications, one must design interacting interface modules that potentially communicate in complex and intricate ways. When designing communicating asynchronous modules, several difficult problems arise. First, even if each individual module can be synthesized correctly, according to the environmental assumptions specified for that module, the composition of the communicating modules may not work properly. Thus, one needs to have a way to model how the modules interact with each other, and to verify that their cooperation is consistent. In addition, means should be provided for communication and synchronization at a level higher than signal transitions, and for exploiting the communicating nature of these modules in optimization. This paper proposes a communicating Petri net model for describing communicating asynchronous modules. Each module is modeled by means of a labeled Petri net that extends the widely used Signal Transition Graph model by providing an abstract synchronization mechanism based on rendez-vous semantics. This enables the designer to specify high-level communication as well as low-level details such as signal transitions. Abstract synchronization events are expanded automatically to low-level handshake signals. We have developed a new algebra for communicating Petri nets that is applicable to general Petri nets, involves no unfolding, and defines hiding as generalized net contraction. We have developed methods based on this formal algebra that can be used to manipulate communicating interface modules, to verify their consistency, and to use them as a basis for optimizations. 1.

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.

W e describe a computationally ecient s c heme to approximate average switching activity in sequential circuits which requires the solution of a non-linear system of equations of size N, where the variables correspond to state line probabilities.W e show that the approximation method is within 3% of the exact Chapman-Kolmogorov method, but is orders of magnitude faster for large circuits.Previous sequential switching activity estimation methods can have signi cantly greater inaccuracies.

An important practical approach to automatic verification of finite state concurrent systems is temporal logic model checking.However, a major barrier towards wider application of such methods is the state explosion problem that often occurs during the composition of complex communicating systems.In addition to being large, many systems have very deep state spaces as well.In this paper, we propose an abstraction method based on time abstraction which can significantly reduce both the size as well as the depth of the state space that must be explored during model checking.It is especially suited for applications involving systems that are loosely coupled in the sense that communication activity is relatively sparse, such as applications involving DSPs, which have large intervals of autonomous processing, with communication activity in between.All properties expressible with the temporal logic CTL or CTL -X are strongly preserved under the proposed abstraction.In particular, we give a method that can replace a chain of states by a single state with a time label.The abstracted model is represented by means of a timed label transition system model.We give a composition algorithm for composing the individually time abstracted models to form a global model that can be converted back to a conventional, but potentially much reduced,state space suitable for model checking.Furthermore, a similar approach can be followed in dealing with wait states in which a system is idling while waiting for an escape signal.For many cases, our approach is successful in alleviating the state explosion problem that often arises in composition of communicating systems.

A method is presented for minimal sizing and verification of communication buffers in an environment of communicating concurrent processes. Methods described in the literature based on lifetime analysis techniques are mainly suited for sizing buffers in a network of processes with non-conditional interactions. We consider a more general problem where the execution of each process inherently depends on complex interactions with other processes as well as its internal conditional behavior and propose the use of implicit state enumeration techniques to solve buffer sizing and verification for this case. A model of the network of processes and buffers is introduced that is transformed into a network of finite state machines by modeling communicating buffers as counters. The transformed network forms a finite state space model on which implicit state space exploration algorithms are applied. The model allows us to handle the buffer sizing and verification problems with processes that operate on different, but related clocks. To reduce the complexity of the state space, abstraction techniques can be used to produce simplified versions of finite state machines that hide away unnecessarily detailed information. The feasibility of the proposed approach is demonstrated by a practical example.

An incompletely specified function can be given by an interval (g, h) or alternatively by a function f and a don't care set d. Depending on the assignment of don't cares, a different compatible function with a possibly support set may be derived. In this paper, efficient symbolic algorithms based on BDDs are presented for finding a compatible function with the minimum support. Efficient solution to this problem has important application in FPGA synthesis.>

Most research in logic synthesis has mainly focussed on area and delay optimizations. In this paper, we focus on the problem of mapping a technology independent circuit to a library of gates such that power is minimized while satisfying some user-specific timing constraints. Such timing constraints can often be rather stringent. We present a new technology mapping algorithm based on extending the dynamic programming paradigm for low-power under timing constraints. The effectiveness of this algorithm is based on two key observations: first, the switching activities of different nodes in a network can vary significantly; and second, the power contribution from a node is directly proportional to its switching activity. Therefore, it is possible to significantly optimize for low power by minimizing the fanout load of "high" switching nodes whenever possible, and trying to compensate instead for delay at the fanout of "lower" switching nodes. In addition to extending dynamic programming for low power under timing constraints, we have also developed optimization techniques that can be used to optimize further for low power and delay. We present experimental results on a large set of standard benchmarks to demonstrate that substantial optimization is possible.>

A constraint satisfaction framework is proposed that can guarantee necessary and sufficient conditions for a state graph assignment to result in a transformed state graph that is race-free. Performing transformations at the state graph level has the advantage that the requirements imposed on the initial signal transition graph (STG) are very weak. Unlike previous methods, the initial STG need not be a live, safe, free choice net. The only requirement is that the corresponding initial state graph should be finite and connected, and have a consistent state assignment. Hence, a very broad range of STGs can be synthesized. The transformation achievable using the proposed framework correspond to very complex transformations on STGs. Even transformations that convert a free choice net into a correct non-free choice net, and a 1-safe net into a correct 2-safe net are feasible. Addition of transitions that do not follow the Petri net firing rule is also possible.>

An optimization method, called fast simulated diffusion (FSD), is proposed to solve a multiminimial optimization problem on multidimensional continuous space. The algorithm performs a greedy search and a random search alternately and can find the global minimum with a practical success rate. An efficient hill-descending method employed as the greedy search in the FSD is proposed. When the FSD is applied to a set of standard test functions, it shows an order of magnitude faster speed than the conventional simulated diffusion. Some of the optimization problems encountered in system and VLSI designs are classified into multioptimal problems. The proposed FSD is successfully applied to a MOSFET parameter extraction problem with a deep submicron MOSFET.>

A novel representation called an equivalence class characterization function is defined. It can implicitly represent all equivalence classes with a compact characteristic function that will have at most n outputs. Using binary decision diagrams (BDDs) and the concept of the equivalence class characterization function, very large problem instances can be represented. For manipulating equivalence classes efficiently, a Boolean operator called a compatible projection operator is proposed. Conceptually, the compatible projection operator is used to uniquely select a single element from each equivalence class to characterize the class. In manipulating equivalence classes, the compatible projection operator is used to implicitly derive an encoding function from the equivalence relation that encodes the equivalence class information symbolically. An efficient implementation is described based on BDDs that is applied to very large problem instances.>

A novel state assignment algorithm, called MUSE (multilevel symbolic encoding), for the encoding of FSMs (finite state machines) targeted for multilevel implementation is presented. Novel methods are discussed for the computation of state pair costs that are based onmultilevel algebraic structures derived from the one hot encoded state machine by purely algebraic techniques. Both Boolean (distance-1 MERGE and consensus) and algebraic (SUB-EXPRESSION EXTRACTION and CO-KERNEL EXTRACTION) operations are used to calculate the encoding affinity of state pairs, and account for face embedding constraints as well. Both heuristic and simulated annealing encoding techniques are used.>

The problem of minimizing symbolic relations is addressed. The relevance of this problem in the field of optimal encoding is shown by examples. A binate covering formulation of the optimization problems involved is given, for which several algorithms are available. A novel method is proposed which is based on binary decision diagrams (BDDs) and the authors show how the covering problem can be solved in linear time in that case.>

The authors address the problem of computing sequential don't cares that arise in the context of multi-level sequential networks and their use in sequential logic synthesis. The key to their approach is the use of binary decision diagram (BDD)-based implicit state space enumeration techniques and multi-level combinational simplification procedures. Using the algorithms described, exact sequential don't care sets for circuits with over 10/sup 68/ states have been successfully computed.>

The authors propose a novel method based on transition relations that only requires the ability to compute the BDD (binary decision diagram) for f/sub i/ and outperforms O. Coudert's (1990) algorithm for most examples. The method offers a simple notational framework to express the basic operations used in BDD-based state enumeration algorithms in a unified way and a set of techniques that can speed up range computation dramatically, including a variable ordering heuristic and a method based on transition relations.>

A technique, called circuit disassembly, for transforming a mask-level description into an equivalent symbolic layout is described. This technique has been implemented in a program that can handle physical layouts containing arbitrary Manhattan geometry. Circuits designed using mask-level layout systems can be disassembled automatically, independent of the circuit technology, into a symbolic environment. Once converted, the disassembled layout can be manipulated further by existing symbolic design or verification tools. A key motivation for symbolic representation is the relative ease of retargeting designs for new process technologies. Industrial symbolic compaction systems can be used for this purpose. The formulation of the problem consists of two major steps: device extraction and net decomposition. The first step involves extracting transistors and contacts from the layout. New symbolic primitives are generated if available library elements are insufficient. The second step aims at synthesizing symbolic wires from the remaining mask geometry for interconnecting the circuit primitives.>

A generalized approach to the constrained cubical embedding problem is described. The generalized solver is separated from the constraints so that application-specific constraints and objective criteria can be easily incorporated. The approach has been implemented in an open system package, called CUBIC, that incorporates a highly interactive graphical interface for new problem explorations. Experiments on a large set of design examples demonstrate that the generalized approach can produce results comparable or superior to specialized methods, in similar CPU time.>

A new tool called a circuit disassembler has been developed to transform a mask level layout into an equivalent symbolic layout. This technique has been implemented in the program called KAHLUA that can handle mask layout containing arbitrary Manhattan geometry and is independent of the circuit technology. Circuits designed using physical layout systems can be automatically disassembled into a symbolic environment. Once converted, the disassembled cells can be manipulated further by any existing symbolic design or verification tools. In particular, these cells can be automatically remapped for a new technology. Our formulation of the problem consists of two major stages: device extraction, and net decomposition. In the first stage the transistors and contacts are extracted from the layout to form leaf cells. In the second stage a set of symbolic wires is derived from the remaining interconnect geometry. KAHLUA has been tested on a wide range of physical cells and has produced high quality results with modest execution times. An additional feature of the technique include the ability to disassemble hierarchically, which makes disassembling large layouts feasible.