Technology mapping is an essential step bridging logic synthesis and physical design in the electronic design automation (EDA) flow. However, technology mapping algorithms often assume a simplified delay model and may not faithfully optimize the circuit under a realistic cost function involving area, delay, and power objectives. In this work, we introduce GradMap, a gradient-descent-based technology mapping framework that integrates a differentiable static timing analysis (STA) engine with a linear delay model for accurate delay estimation. Additionally, it enables simultaneous buffer insertion and gate sizing during technology mapping, providing a holistic optimization solution. Experimental results show that the new method achieves an average improvement of 7% in area-driven optimization, 33% in delay-driven optimization, and 25% in area-delay-product optimization compared to the ABC technology mapper. We note that although the gradient-descent method has significant runtime overhead compared to the highly efficient ABC mapper, it is highly parallelizable with GPU acceleration (in a way similar to the neural network training process), besides attaining high optimization quality far beyond ABC’s ability.

Utilizing multibit flip-flops (MBFFs) is one of the most effective power optimization techniques in modern nanometer integrated circuit design. Most of the previous works apply MBFFs without doing placement refinement of combinational logic cells. Such problem formulation may result in less power reduction due to tight timing constraints with fixed combinational logic cells. This paper introduces a novel placement flow with clock-tree aware flip-flop (FF) merging and MBFF generation, and proposes the corresponding algorithms to simultaneously minimize FF power and clock latency when applying MBFFs during placement. Experimental results based on the IWLS-2005 benchmark show that our approach is very effective in not only FF power but also clock latency minimization without degrading circuit performance. To our best knowledge, this is also the first work in the literature which considers clock trees when generating MBFFs during placement.

We aimed to build up a visualized data analysis process to detect potential tax evasion caused by bogus business entities. Relevant datasets of bogus business entities were extracted from large databases of 8 different systems at the Fiscal Information Agency for tax evasion pattern recognition and behavior analysis. Visualized data analysis not only helped on identifying bogus business entities, but also helped to establish a detection mechanism to discover potential tax evasion for the government.

Applying clock gates (CGs) and multi-bit flip-flops (MBFFs) are two of the most effective techniques for low power clock network design. Some previous works had proposed to optimize clock network with either CGs or MBFFs, but none of them simultaneously considers both CGs and MBFFs during clock network optimization. Although CGs and MBFFs can be optimized separately, the resulting dynamic power may not be optimal. This paper presents the first problem formulation in the literature for gated clock network optimization with simultaneous CG cloning and FF merging. To effectively solve the problem, a novel optimization flow consisting of MBFF-aware CG cloning, CG-based FF merging, and MBFF and CG placement optimization is introduced. Experimental results show that the proposed flow results in better dynamic power and clock wirelength compared with other flows which optimize gated clock network with CGs and MBFFs separately.

Designing a lifetime-maximization routing in wireless sensor networks poses a great challenge mainly due to unreliable wireless links and limited power supply. Recently, two natural advantages of opportunistic routing, i.e., path diversity and the improvement of transmission reliability, are exploited to develop a lifetime-extended opportunistic routing for wireless sensor networks. Besides, asynchronous sleep-wake scheduling is an effective mechanism to reduce energy consumption by appropriately arranging sensor nodes to sleep. Hence, in this paper, we propose a joint design of asynchronous sleep-wake schedules and opportunistic routing, called ASSORT, to maximize the network lifetime. Simulation results show that ASSORT effectively achieves network lifetime extension compared with other routing schemes.

Utilizing multi-bit flip-flops (MBFFs) is one of the most effective power optimization techniques in modern nanometer integrated circuit (IC) design. Most of the previous work apply MBFFs without doing placement refinement of combinational logic cells. Such problem formulation may result in less power reduction due to tight timing constraints with fixed combinational logic cells. This paper introduces a novel placement flow with clock-tree aware flip-flop merging and MBFF generation, and proposes the corresponding algorithms to simultaneously minimize flip-flop power and clock latency when applying MBFFs during placement. Experimental results based on the IWLS-2005 benchmark show that our approach is very effective in not only flip-flop power but also clock latency minimization without degrading circuit performance. To our best knowledge, this is also the first work in the literature which considers clock trees during flip-flop merging and MBFF generation.

Flexible channels enable Access Points (AP) and clients to determine channel widths and their center frequencies. The key challenge in flexible channels is how to determine proper channel width and center frequency for each link demands such that the overall system throughput could be improved. In this work, we introduce a distributed flexible channel assignment algorithm, DFCA. Different from prior researches, DFCA does link-based channel assignment instead of AP-based or packet-based. This is because that the packet-based method could incur heavy overhead, while the AP-based method is not able to determine the interfering relation between links precisely. In addition, the transmission weight of a link is proposed; with the help of the transmission weight, channel width, center frequency and interference relation to neighboring nodes, DFCA is able to accurately predict that link throughput prior to the channel assignment. Results show that DFCA could outperform traditional fixed channel assignment approaches and the AP-based flexible channel assignment algorithm. Even compared with FLUID[1], which is a packet-based channel assignment approach with assist of a central controller, DFCA is able to achieve comparable (at least 93%) throughput by using only local information rather than global knowledge.

Adaptation of modulation and transmission bit-rates for video multicast in a multirate wireless network is a challenging problem because of network dynamics, variable video bit-rates, and heterogeneous clients who may expect differentiated video qualities. Prior work on the leader-based schemes selects the transmission bit-rate that provides reliable transmission for the node that experiences the worst channel condition. However, this may penalize other nodes that can achieve a higher throughput by receiving at a higher rate. In this work, we investigate a rate-adaptive video multicast scheme that can provide heterogeneous clients differentiated visual qualities matching their channel conditions. We first propose a rate scheduling model that selects the optimal transmission bit-rate for each video frame to maximize the total visual quality for a multicast group subject to the minimum-visual-quality-guaranteed constraint. We then present a practical and easy-to-implement protocol, called QDM, which constructs a cluster-based structure to characterize node heterogeneity and adapts the transmission bit-rate to network dynamics based on video quality perceived by the representative cluster heads. Since QDM selects the rate by a sample-based technique, it is suitable for real-time streaming even without any preprocess. We show that QDM can adapt to network dynamics and variable video-bit rates efficiently, and produce a gain of 2-5 dB in terms of the average video quality as compared to the leader-based approach.

Since data in underwater sensor networks (UWSNs) is transmitted by acoustic signals, the characteristics of a UWSN are different from those of a terrestrial sensor network. Specifically, due to the high propagation delay of acoustic signals in UWSNs, referred as spatial-temporal uncertainty, current terrestrial MAC schemes do not work well in UWSNs. Hence, we consider spatial-temporal uncertainty in the design of an energy-efficient TDMA-based MAC protocol for UWSNs. We first translate the TDMA-based scheduling problem in UWSNs into a special vertex-coloring problem in the context of a spatial-temporal conflict graph (ST-CG) that describes explicitly the conflict delays among transmission links. With the help of the ST-CG, we propose two novel heuristic approaches: 1) the traffic-based one-step trial approach (TOTA) to solve the coloring problem in a centralized fashion; and for scalability, 2) the distributed traffic-based one-step trial approach (DTOTA) to assign the data schedule for tree-based routing structures in a distributed manner. In addition, a mixed integer linear programming (MILP) model is derived to obtain a theoretical bound for the TDMA-based scheduling problem in UWSNs. Finally, a comprehensive performance study is presented, showing that both TOTA and DTOTA guarantee collision-free transmission. They thus outperform existing MAC schemes such as S-MAC, ECDiG, and T-Lohi in terms of network throughput and energy consumption.

ABSTRACT The utilization of limited energy in wireless sensor networks (WSNs) is the critical concern, whereas the effectiveness of routing mechanisms substantially influence energy usage. We notice that two common issues in existing specific routing schemes for WSNs are that (i) a path may traverse through a specific set of sensors, draining out their energy quickly and (ii) packet retransmissions over unreliable links may consume energy significantly. In this paper, we develop an energy‐efficient routing scheme (called EFFORT) to maximize the amount of data gathered in WSNs before the end of network lifetime. By exploiting two natural advantages of opportunistic routing, that is, the path diversity and the improvement of transmission reliability, we propose a new metric that enables each sensor to determine a suitable set of forwarders as well as their relay priorities. We then present EFFORT, a routing protocol that utilizes energy efficiently and prolongs network lifetime based on the proposed routing metric. Simulation results show that EFFORT significantly outperforms other routing protocols. Copyright © 2011 John Wiley & Sons, Ltd.

Applying multi-bit flip-flops (MBFFs) for clock power reduction in modern nanometer ICs has been becoming a promising lower-power design technique. Many previous works tried to utilize as more MBFFs with larger bit numbers as possible to gain more clock power saving. However, an MBFF with a larger bit number may lead to serious crosstalk due to the close interconnecting wires belonging to different signal nets which are connected to the same MBFF. To address the problem, this paper analyzes, evaluates, and compares the relationship between power consumption and crosstalk when applying MBFFs with different bit numbers. To solve the addressed problem, a novel crosstalk-aware power optimization approach is further proposed to optimize power consumption while satisfying the crosstalk constraint. Experimental results show that the proposed approach is very effective in crosstalk avoidance when applying MBFFs for power optimization. To our best knowledge, this is also the first work in the literature that considers the crosstalk effect for the MBFF application.

Because of marketing demand of user-centric video dissemination, promoting video content via interactive distribution platforms has received considerable attention recently. In addition, the preferences of clients are heterogenous and dynamic, effectively utilizing the network bandwidth to distribute user-centric content becomes a challenging problem, especially when the number of users in the systems scale up. Therefore, we propose a P2P-based distribution platform, called Bulldozer, which enable clients to cooperatively propagate user-centric video content in a large scale environment, and better utilizes peers upload bandwidth to share the server traffic load. Bulldozer consists of two components: 1) Clip Scheduling phase schedules the playing order of videos for each individual user, and 2) Bandwidth Allocation phase allocates users upload bandwidths to distribute videos among clients. Finally, simulation results show that Bulldozer can effectively reduce the peak traffic load of the server.

Optimization for power is always one of the most important design objectives in modern nanometer integrated circuit design. Recent studies have shown the effectiveness of applying multi-bit flip-flops to save the power consumption of the clock network. This paper presents: 1) a novel design methodology of applying multi-bit flip-flops at the post-placement stage, which can be seamlessly integrated in modern design flow; 2) a new problem formulation for post-placement optimization with multi-bit flip-flops; 3) flip-flop clustering and placement algorithms to simultaneously minimize flip-flop power consumption and interconnecting wirelength; and 4) a progressive window-based optimization technique to reduce placement deviation and improve runtime efficiency of our algorithms. Experimental results show that our algorithms are very effective in reducing not only flip-flop power consumption but also clock tree and signal net wirelength. Consequently, the power consumption of the clock network is minimized.

Optimization for power is always one of the most important design objectives in modern nanometer IC design. Recent studies have shown the effectiveness of applying multi-bit flip-flops to save the power consumption of the clock network. However, all the previous works applied multi-bit flip-flops at earlier design stages, which could be very difficult to carry out the trade-off among power, timing, and other design objectives. This paper presents a novel power optimization method by incrementally applying more multi-bit flip-flops at the post-placement stage to gain more clock power saving while considering the placement density and timing slack constraints, and simultaneously minimizing interconnecting wirelength. Experimental results based on the industry benchmark circuits show that our approach is very effective and efficient, which can be seamlessly integrated in modern design flow.

Lifetime-maximization is the critical concern for wireless sensor networks (WSNs). We notice that two common issues in existing routing schemes for WSNs are that (1) a path may traverse through a fixed set of sensors, draining out their energy quickly, and (2) packet retransmissions over an unreliable link of any fixed-path may consume energy significantly. In this paper, we exploit two natural advantages of opportunistic routing, i.e., path diversity and the improvement of transmission reliability, to develop a distributed routing scheme (called EFFORT) for prolonging the network-lifetime of a WSN. Specifically, a new metric is proposed to assist each sensor in determining a suitable set of forwarders as well as their priorities and, thus, enables EFFORT to extend the network-lifetime. Simulation results show that EFFORT effectively achieves network-lifetime extension compared to other routing protocols.

In wireless sensor networks (WSNs), due to scarce resources like energy, computational capability and storage space as well as rapid change in wireless link characteristics such as signal strength, interference, and multi-path propagation, how to provide a reliable data transmission in WSNs while prolonging the network lifetime as long as possible is an important and challenging issue. In general, there are several approaches, e.g., automatic repeat request, multi-path routing and source coding, used for providing reliable data transfer in WSNs. We note that the overhead and performance of such end-to-end single-path approaches are often dominated by some poor-quality links or nodes on the path. That is, these traditional approaches are not able to quickly and properly react in this multi-hop wireless environment. To cope with the above issues, in this work we would like to propose an efficient reliable data transfer scheme with network coding for WSNs. To guarantee expected reliability with appropriate overhead, we not only derive an analytic model to estimate the proper amount of redundancy, but also propose the cluster-based and distributed scheme to dynamically adjust the redundancy at each hop. Through simulations in ns2, our results show that, compared with existing reliable data transfer schemes, our approach can achieve the required reliability with significantly fewer transmissions.

Underwater sensor networks (UWSNs) have attracted a lot of attention recently. Since data in UWSNs are transmitted by acoustic signals, the characteristics of a UWSN are different from those of a terrestrial sensor network. In other words, the high propagation delay of acoustic signals in UWSNs causes spatial-temporal uncertainty, and makes transmission scheduling in UWSNs a challenging problem. Hence, in this paper, we propose a spatial-temporal MAC scheduling protocol, called ST-MAC, which is designed to overcome spatial-temporal uncertainty based on TDMA-based MAC scheduling for energy saving and throughput improvement. We construct thespatial-temporalconflictgraph(ST-CG) to describe the conflict delays among transmission links explicitly, and model ST-MAC as a new vertex coloring problem of ST-CG. We then propose a novel heuristic, called thetraffic-basedone-steptrialapproach(TOTA), to solve the coloring problem. In order to obtain the optimal solution of the scheduling problem, we also derive a mixed integer linear programming (MILP) model. Finally, we present a comprehensive performance study via simulations. The results show that ST-MAC can perform better than existing MAC schemes (such as S-MAC, ECDiG, and T-Lohi) in terms of the network throughput and energy cost.

Since the effectiveness of the routing scheme directly affects resource (e.g. energy, bandwidth, and memory) usage in wireless sensor networks, research works on routing protocols have received considerable attention recently. In this paper, we propose a location-free point-to-point routing scheme, called virtual domain and coordinate routing (VDCR), in wireless sensor networks. VDCR applies the concepts of the virtual domain and the virtual coordinate to design its distributed assignment protocol and the location-free routing protocol. That is, the assignment protocol assigns each sensor node the virtual coordinate to represent the location in a network and the virtual domain to maintain the information about the existing shortest path that has been established during the coordinate assignment. Our VDCR is able to efficiently discover the routing path based on the assigned domains and coordinates. The simulations show that the routing path of VDCR is shorter than ABVCap by 62%-70%. Besides, VDCR require 63%-89% preprocess overhead of ABVCap. For realistic network topologies with obstacles, VDCR can improve the routing path by 64% and up to 96%, compared with GPSR that requires physical location information.

We propose an indexing technique for fast retrieval of similar subsequences using time warping distances. A time warping distance is a more suitable similarity measure than the Euclidean distance in many applications, where sequences may be of different lengths or different sampling rates. Our indexing technique uses a disk-based suffix tree as an index structure and employs lower-bound distance functions to filter out dissimilar subsequences without false dismissals. To make the index structure compact and thus accelerate the query processing, we convert sequences of continuous values to sequences of discrete values via a categorization method and store only a subset of suffixes whose first values are different from their preceding values. The experimental results reveal that our proposed technique can be a few orders of magnitude faster than sequential scanning.

A knowledge-based approach to retrieve medical images by feature and content with spatial and temporal constructs is developed. Selected objects of interest in an image are segmented and contours are generated. Features and content are extracted and stored in a database. Knowledge about image features can be expressed as a type abstraction hierarchy (TAH), the high-level nodes of which represent the most general concepts. Traversing TAH nodes allows approximate matching by feature and content if an exact match is not available. TAHs can be generated automatically by clustering algorithms based on feature values in the databases and hence are scalable to large collections of image features. Since TAHs are generated based on user classes and applications, they are context- and user-sensitive. A knowledge-based semantic image model is proposed to represent the various aspects of an image object's characteristics. The model provides a mechanism for accessing and processing spatial, evolutionary and temporal queries. A knowledge-based spatial temporal query language (KSTL) has been developed that extends ODMG's OQL and supports approximate matching of features and content, conceptual terms and temporal logic predicates. Further, a visual query language has been developed that accepts point-click-and-drag visual iconic input on the screen that is then translated into KSTL. User models are introduced to provide default parameter values for specifying query conditions. We have implemented the KMeD (Knowledge-based Medical Database) system using these concepts.

A knowledge based approach is introduced for retrieving images by content. It supports the answering of conceptual image queries involving similar-to predicates, spatial semantic operators, and references to conceptual terms. Interested objects in the images are represented by contours segmented from images. Image content such as shapes and spatial relationships are derived from object contours according to domain specific image knowledge. A three layered model is proposed for integrating image representations, extracted image features, and image semantics. With such a model, images can be retrieved based on the features and content specified in the queries. The knowledge based query processing is based on a query relaxation technique. The image features are classified by an automatic clustering algorithm and represented by Type Abstraction Hierarchies (TAHs) for knowledge based query processing. Since the features selected for TAH generation are based on context and user profile, and the TAHs can be generated automatically by a clustering algorithm from the feature database, our proposed image retrieval approach is scalable and context sensitive. The performance of the proposed knowledge based query processing is also discussed.