Non-unique probe selection and group testing
A minimization problem that has arisen from the study of non-unique probe selection with group testing technique is as follows: Given a binary matrix, find a d-disjunct submatrix with the minimum number of rows and the same number of columns. We show that when every probe hybridizes to at most two viruses, i.e., every row contains at most two 1s, this minimization is still MAX SNP-complete, but has a polynomial-time approximation with performance ratio 1+2/(d+1). This approximation is constructed based on an interesting result that the above minimization is polynomial-time solvable when every probe hybridizes to exactly two viruses.

title: On the construction of 2-connected virtual backbone in wireless networks
abstract: Virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem in ad hoc networks. Since the nodes in the virtual backbone need to carry other node's traffic, and node and link failure are inherent in wireless networks, it is desirable that the virtual backbone is fault tolerant. In this paper, we propose a new algorithm called Connecting Dominating Set Augmentation (CDSA) to construct a 2-connected virtual backbone which can resist the failure of one wireless node. We show that CDSA has guaranteed quality by proving that the size of the CDSA constructed 2-connected backbone is within a constant factor of the optimal 2-connected virtual backbone size. Through extensive simulations, we demonstrate that in practice, CDSA can build a 2-connected virtual backbone with only small overhead.

title: Coverage problems in wireless sensor networks: designs and analysis
abstract: One fundamental problem in wireless sensor networks is the coverage problem, which reflects the quality of service that can be provided by a particular sensor network. The coverage problem is defined from several points of view due to a variety of sensor networks and a wide-range of their applications. Several different designs and formulations of the coverage problem have been proposed. They are subject to various topics such as types of interest regions (areas versus targets) and different network constraints, such as fault tolerance and bandwidth limitation. In this paper, we survey the state-of-the-art coverage formulations with an objective of maximising network lifetime. In particular, we present an overview and analysis of the solutions proposed in recent research literature.

title: Optimization scheme for sensor coverage scheduling with bandwidth constraints
abstract: Wireless Sensor Network has attracted a lot of attentions due to its broad applications in recent years and also introduces many challenges. Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a “trade-off” scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in (Cheng et al. in INFOCOM’ 05, 2005).

title: Improved construction for pooling design
abstract: Pooling design is a mathematical tool with many applications in molecular biology, specially to reduce the number of tests for DNA library screening. In this note, we study construction of pooling design and present an improvement to a recent new construction given by Du et al. ( 2006).

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: 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: 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: On-chip Bus Thermal Analysis and Optimization
abstract: As technology scales, increasing clock rates, decreasing interconnect pitch, and the introduction of low-k dielectrics have made self-heating of the global interconnects an important issue in VLSI design. In this paper, we study the self-heating of on-chip buses and show that the thermal impact due to self-heating of on-chip buses increases as technology scales, thus motivating the need of finding solutions to mitigate this effect. Based on the theoretical analysis, we propose an irredundant bus encoding scheme for on-chip buses to tackle the thermal issue. Simulation results show that our encoding scheme is very efficient to reduce the on-chip bus temperature rise over substrate temperature, with much less overhead compared to other low power encoding schemes.

title: A Novel Criticality Computation Method in Statistical Timing Analysis
abstract: The impact of process variations increases as technology scales to nanometer region. Under large process variations, the path and arc/node criticality [18] provide effective metrics in guiding circuit optimization. To facilitate the criticality computation considering the correlation, we define the critical region for the path and arc/node in a timing graph, and propose an efficient method to compute the criticality for paths and arcs/nodes simultaneously by a single breadth-first graph traversal during the backward propagation. Instead of choosing a set of paths for analysis prematurely, we develop a new property of the path criticality to prune those paths with low criticality at very earlier stages, so that our path criticality computation method has linear complexity with respect of the timing edges in a timing graph. To improve the computation accuracy, cutset and path criticality properties are exploited to calibrate the computation results. The experimental results on ISCAS benchmark circuits show that our criticality computation method can achieve high accuracy with fast speed.

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.