6291223
Interconnect implications of growth-based structural models for VLSI circuits
Power-law scaling phenomena that govern VLSI circuits have for several decades formed the foundation of VLSI interconnect estimation.   This research investigates possible alternative power-law phenomena in VLSI circuits.   In particular, we develop new<italic>random growth</italic>models and assess their implications for VLSI interconnect structure.   We assess our models' predictions for<italic>fanout</italic>,<italic>crossing edge</italic>, and<italic>terminal</italic>scaling using test data from 21 industry standard-cell designs with up to 283K cells.   Our work demonstrates the possibility of non-Rent based, yet equally plausible and well-fitting, structural models for VLSI circuits and their interconnections.
5760901
Statistical gate delay calculation with crosstalk alignment consideration
We study gate delay variation caused by crosstalk aggressor alignment, i.e., difference of signal arrival times in coupled neighboring interconnects. This effect is as significant as multiple-input switching on gate delay variation [2]. We establish a functional relationship between driver gate delay and crosstalk alignment by deterministic circuit simulation, and derive closed form formulas for statistical distributions of driver gate delay and output signal arrival time.Our proposed method can be smoothly integrated into a static timing analyzer, which runtime is dominated by sampling deterministic delay calculation, while probabilistic computation and updating take constant time. Our experimental results on 70nm technology global interconnect structures and 130nm technology industry designs show respectively 159:4% and 147:4% differences in mean and standard deviation of gate delay without crosstalk aggressor alignment consideration, while our method gives within 2:57% and 3:86% offset in gate output signal arrival time mean and standard deviation, respectively.
18992172
A practical packet reordering mechanism with flow granularity for parallelism exploiting in network processors
Network processors (NP) are usually designed to exploit packet level parallelism where system throughput is aggregated by multiple CPU cores. A serious problem in such a system is packet disordering (PD), which may deteriorate network performance greatly. To address the PD problem, a practical reordering mechanism is put forward in this paper. Different from the traditional reordering methods such as in ATM networks, it uses a central-controlled chain-based mechanism to implement packet reordering with flow granularity. We verify it in FPGA and carry out a series of experiments, where the results show that system throughput can be influenced greatly by traffic patterns. We also demonstrate that the reordering with flow granularity is quite requisite in NP, which can increase the system throughput to a great extent compared to the conventional method with global granularity.
800712
On the autocorrelation structure of TCP traffic
The statistical characteristics of network traffic--in particular the observation that it can exhibit long range dependence--have received considerable attention from the research community over the past few years. In addition, the recent claims that the TCP protocol can generate traffic with long range dependent behavior has also received much attention. Contrary to the latter claims, in this paper we show that the TCP protocol can generate traffic with correlation structures that spans only an analytically predictable finite range of time-scales. We identify and analyze separately the two mechanisms within TCP that are responsible for this scaling behavior: timeouts and congestion avoidance. We provide analytical models for both mechanisms that, under the proper loss probabilities, accurately predict the range in time-scales and the strength of the sustained correlation structure of the traffic sending rate of a single TCP source. We also analyze an existing comprehensive model of TCP that accounts for both mechanisms and show that TCP itself exhibits a predictable finite range of time-scales under which traffic presents sustained correlations. Our claims and results are derived from Markovian models that are supported by simulations. We note that traffic generated by TCP can be misinterpreted to have long range dependence, but that long range dependence is not possible due to inherent finite time-scales of the mechanisms of TCP.
17725194
SPF: to improve the performance of packet-mode scheduling
Recent researches present that packet-mode scheduling may provide overall performance advantages over cell-mode scheduling in input queueing switches. But one significant drawback of existing packet-mode schedulers is that they tend to result in longer waiting time of short packets, whose delay is critical to the performance of IP networks. To mitigate the problem, this paper proposes a simple but effective packet-mode scheduling algorithm called Short Packets First (SPF), studies the corresponding buffering architecture, and evaluates the performance on throughput and packet delay. SPF achieves 100% throughput under an accurate Internet traffic model. Theoretical analysis proves that SPF can reduce the average packet waiting time of short packets as well as overall packets, under the condition of uniform Poisson arrival process and low to medium offered load. Furthermore, extended simulation studies show that SPF is superior to general packet-mode and cell-mode scheduling, especially under heavy offered load.
20672183
An Algorithm to Construct k-Regular k-Connected Graphs with the Maximum k-Diameter
Abstract. Let f(2m,k) be the Maximum k-diameter of k-regular k-connected graphs on 2m vertices. In this paper we give an algorithm and prove that we can construct k-regular k-connected graphs on 2m vertices with the maximum k-diameter using it. We also prove some known results about f(2m,k) and verify that we can get some unknown values of f(2m,k) by our algorithm.
7867063
D-CAPE: distributed and self-tuned continuous query processing
Efficient continuous query processing is critical for many applications, including monitoring remote sensors network traffic management, and online transaction processing. To overcome resource limitations and achieve real-time responsiveness, continuous query systems research focuses on issues such as punctuation-driven operator-state purging [4], load shedding, operator scheduling [7] and plan optimization and on-line migration [9]. However, when real-time yet accurate results are critical such as in stock market analysis, then there is a limitation to what any of the above optimization techniques can accomplish. Hence, distributed processing must be applied to support required scalability. It has been already proven in traditional database systems [3] that distributed processing results in high scale-up and speed-up capabilities due to aggregated resources. The design of a distributed continuous query system is characterized by an extra complexity, considered in the design of our D-Cape engine. In such a system, data streams may be infinite and initial cost statistics about the data streams are typically unknown. Moreover, cost statistics continue to change over time. Our research on distributed stream processing addresses two critical questions: (1) How to initially distribute query plans given little or possibly no cost information, and (2) How to efficiently adapt the query distribution corresponding to runtime environmental changes. Even though research is now under way in designing distributed continuous query systems [2], [1], results to date, as far as we know, are based on simulations. Our work offers empirical results of distributed continuous query processing using an actual software system [5], [6]. D-Cape, a distributed continuous query processing architecture, employs stream query engines over a cluster of shared-nothing processors. We employ a dedicated distribution manager to manage