An Approximation for Minimum Multicast Route in Optical Networks with Nonsplitting Nodes
Consider the problem of computing the minimum-weight multicast route in an optical network with both nonsplitting and splitting nodes. This problem can be reduced to the minimum Hamiltonian path problem when all nodes are nonsplitting, and the Steiner minimum tree problem when all nodes are splitting. Therefore, the problem is NP-hard. Previously, the best known polynomial-time approximation has the performance ratio 3. In this paper, we present a new polynomial-time approximation with performance ratio of 1+ρ, where ρ is the best known approximation performance ratio for the Steiner minimum tree in graph and it has been known that ρ < 1.55.

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: 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: 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: Variation-aware resource sharing and binding in behavioral synthesis
abstract: As technology scales, the delay uncertainty caused by process variations has become increasingly pronounced in deep submicron designs. In the presence of process variations, worst-case timing analysis may lead to overly conservative synthesis, and may end up using excess resources to guarantee design constraints. In this paper, we propose an efficient variation-aware resource sharing and binding algorithm in behavioral synthesis, which takes into account the performance variations for functional units. The performance yield, which is defined as the probability that the synthesized hardware meets the target performance constraints, is used to evaluate the synthesis result. An efficient metric called statistical performance improvement, is used to guide resource sharing and binding. The proposed algorithm is evaluated within a commercial synthesis framework that generates optimized RTL netlists from behavioral specifications. The effectiveness of the proposed algorithm is demonstrated with a set of industrial benchmark designs, which consist of blocks that are commonly used in wireless and image processing applications. The experimental results show that our method achieves an average 33% area reduction over traditional methods, which are based on the worst-case delay analysis, with an average 10% run time overhead.

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: 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: Using MEMS-based storage in computer systems---MEMS storage architectures
abstract: As an emerging nonvolatile secondary storage technology, MEMS-based storage exhibits several desirable properties including high performance, high storage volumic density, low power consumption, low entry cost, and small form factor. However, MEMS-based storage provides a limited amount of storage per device and is likely to be more expensive than magnetic disk. Systems designers will therefore need to make trade-offs to achieve well-balanced designs. We present an architecture in which MEMS devices are organized into MEMS storage enclosures with online spares. Such enclosures are proven to be highly reliable storage building bricks with no maintenance during their economic lifetimes. We also demonstrate the effectiveness of using MEMS as another layer in the storage hierarchy, bridging the cost and performance gap between MEMS storage and disk. We show that using MEMS as a disk cache can significantly improve system performance and cost-performance ratio.

title: Variation-aware task allocation and scheduling for MPSoC
abstract: 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.