Variation-aware task allocation and scheduling for MPSoC
As technology scales, the delay uncertainty caused by process variations has become increasingly pronounced in deep submicron designs. As a result, a paradigm shift from deterministic to statistical design methodology at all levels of the design hierarchy is inevitable . In this paper, we propose a variation-aware task allocation and scheduling algorithm for Multiprocessor System-on-Chip (MPSoC) architectures to mitigate the impact of parameter variations. A new design metric, called performance yield and defined as the probability of the assigned schedule meeting the predefined performance constraints, is used to guide the task allocation and scheduling procedure. An efficient yield computation method for task scheduling complements and significantly improves the effectiveness of the proposed variation-aware scheduling algorithm. Experimental results show that our variation-aware scheduler achieves significant yield improvements. On average, 45% and 34% yield improvements over worst-case and nominal-case deterministic schedulers, respectively, can be obtained across the benchmarks by using the proposed variation-aware scheduler.

title: Soft Error Rate Analysis for Combinational Logic Using an Accurate Electrical Masking Model
abstract: Accurate electrical masking modeling represents a significant challenge in soft error rate analysis for combinational logic circuits. In this paper, we use table lookup MOSFET models to accurately capture the nonlinear properties of submicron MOS transistors. Based on these models, we propose and validate the transient pulse generation model and propagation model for soft error rate analysis. The pulse generated by our pulse generation model matches well with that of HSPICE simulation, and the pulse propagation model provides nearly one order of magnitude improvement in accuracy over the previous models. Using these two models, we propose an accurate and efficient block-based soft error rate analysis method for combinational logic circuits.

title: Variability-driven module selection with joint design time optimization and post-silicon tuning
abstract: Increasing delay and power variation are significant challenges to the designers as technology scales to the deep sub-micron (DSM) regime. Traditional module selection techniques in high level synthesis use worst case delay/power information to perform the optimization, and therefore may be too pessimistic such that extra resources are used to guarantee design requirements. Parametric yield, which is defined as the probability of the synthesized hardware meeting the performance/power constraints, can be used to guide design space exploration. The parametric yield can be effectively improved by combining both design-time variation-aware optimization and post silicon tuning techniques (such as adaptive body biasing (ABB)). In this paper, we propose a module selection algorithm that combines design-time optimization with post- silicon tuning (using ABB) to maximize design yield. A variation-aware module selection algorithm based on efficient performance and power yield gradient computation is developed. The post silicon optimization is formulated as an efficient sequential conic program to determine the optimal body bias distribution, which in turn affects design-time module selection. The experiment results show that significant yield can be achieved compared to traditional worst-case driven module selection technique. To the best of our knowledge, this is the first variability-driven high level synthesis technique that considers post-silicon tuning during design time optimization.

title: Optimal topology exploration for application-specific 3D architectures
abstract: As technology scales, increasing interconnect costs make it necessary to consider alternate ways of building integrated circuits. One promising option along this direction is 3D architectures where a stack of multiple device layers, with direct vertical tunneling through them, are put together on the same chip. In this paper, we explore how processor cores and storage blocks can be placed in a 3D architecture to minimize data access costs under temperature constraints. This process is referred to as the topology exploration. Using integer linear programming, we compare the best 2D placement with the best 3D placement, and show through experiments with both single-core and multicore systems that the 3D placement generates much better results (in terms of data access costs) under the same temperature bounds. We also discuss the tradeoffs between temperature constraint and data access costs

title: Embedded Multi-Processor System-on-chip (MPSoC) design considering process variations
abstract: As technology scales, the delay uncertainty caused by process variations has become increasingly pronounced in deep sub-micron designs. As a result, a paradigm shift from deterministic to statistical design methodology at all levels of the design hierarchy is inevitable (Borkar, 2005). As part of two NSF projects (NSF CNS CAREER 0643902 and NSF CNS 0720659), a variation-aware task allocation and scheduling method for multiprocessor system-on-chip (MPSoC) architectures is proposed, to mitigate the impact of parameter variations. A new design metric, called performance yield and defined as the probability of the assigned schedule meeting the predefined performance constraints, is used to guide the task allocation and scheduling procedure. An efficient yield computation method for task scheduling complements and significantly improves the effectiveness of the proposed variation-aware scheduling algorithm. Experimental results show that our variation-aware scheduler achieves significant yield improvements.

title: Dependability analysis of nano-scale FinFET circuits
abstract: FinFET technology has been proposed as a promising alternative for deep sub-micro bulk CMOS technology, because of its better scalability. Previous works have studied the performance or power advantages of FinFET circuits over bulk CMOS circuits. This paper provides the dependability analysis of FinFET circuits, studying the soft error vulnerability of FinFET circuits and the impact of process variation. Our experiments compare FinFET circuits against bulk CMOS circuits in both 32 nm and 45 nm technologies, showing that FinFET circuits have better dependability and scalability, which is indicated by better soft error immunity and less impact of process variation. It is concluded that FinFET-based circuit design is more robust than the bulk CMOS based circuit design

title: OBFS: A File System for Object-Based Storage Devices
abstract: The object-based storage model, in which files are made up of o ne or more data objects stored on self-contained Object-Based Storage Devices (OSDs), is em erging as an architecture for distributed storage systems. The workload presented to the OSDs will be q uite different from that of generalpurpose file systems, yet many distributed file systems employ general-purpose file systems as their underlying file system. We present OBFS, a small and highly ef ficient file system designed for use in OSDs. Our experiments show that our user-level implement ation of OBFS outperforms Linux Ext2 and Ext3 by a factor of two or three, and while OBFS is 1/25 the size of XFS, it provides only slightly lower read performance and 10%‐40% higher write pe rformance.

title: File System Workload Analysis For Large Scientific Computing Applications
abstract: Parallel scientific applications require high-performance I/O support from underlying file systems. A comprehensive understanding of the expected workload is therefore essential for the design of high-performance parallel file systems. We re-examine the workload characteristics in parallel computing environments in the light of recent technology advances and new applications. We analyze application traces from a cluster with hundreds of nodes. On average, each application has only one or two typical request sizes. Large requests from several hundred kilobytes to several megabytes are very common. Although in some applications small requests account for more than 90% of all requests, almost all of the I/O data are transferred by large requests. All of these applications show bursty access patterns. More than 65% of write requests have inter-arrival times within one millisecond in most applications. By running the same benchmark on different file models, we also find that the write throughput of using an individual output file for each node exceeds that of using a shared file for all nodes by a factor of 5. This indicates that current file systems are not well optimized for file sharing.

title: Greedy Approximation Algorithms
abstract: Greedy strategy is a simple and natural method in the design of approximation algorithms. This chapter presents greedy approximation algorithms for very broad classes of maximization problems and minimization problems and analyzes their approximation bounds. A number of applications of these greedy approximation algorithms are also described in this chapter. For many applications, the greedy approximation algorithm can achieve the best known approximation bound in a straightforward manner. For some applications, they have different formulations, and the corresponding greedy approximation algorithms have different approximation bounds. In addition, some applications can have better approximation algorithm than the greedy approximation algorithm.

title: A Real-Time Network Traffic Profiling System
abstract: This paper presents the design and implementation of a real-time behavior profiling system for high-speed Internet links. The profiling system uses flow-level information from continuous packet or flow monitoring systems, and uses data mining and information-theoretic techniques to automatically discover significant events based on the communication patterns of end-hosts. We demonstrate the operational feasibility of the system by implementing it and performing extensive benchmarking of CPU and memory costs using a variety of packet traces from OC-48 links in an Internet backbone network. To improve the robustness of this system against sudden traffic surges such as those caused by denial of service attacks or worm outbreaks, we propose a simple yet effective filtering algorithm. The proposed algorithm successfully reduces the CPU and memory cost while maintaining high profiling accuracy.

title: On greedy construction of connected dominating sets in wireless networks
abstract: Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone. Constructing a minimum CDS is NP-hard. In this paper, we propose a new greedy algorithm, called S-MIS, with the help of Steiner tree that can construct a CDS within a factor of 4:8 þ ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S-MIS with its variation which is rS-MIS. The simulation shows that the sizes of the CDSs generated by S-MIS and rS-MIS are almost the same.