Remote collaboration tools for conferencing and presentation are gaining significant popularity during the COVID-19 pandemic period. Most prior work has issues, such as a) limited support for media types, b) lack of interactivity, for example, an efficient replay mechanism, c) large bandwidth consumption for screen sharing tools. In this paper, we propose a general-purpose multimedia collaboration platform-CWcollab. It supports collaboration on general multimedia by using simple messages to represent media controls with an object-prioritized synchronization approach. Thus, CWcollab can not only support fine-grained accurate collaboration, but also rich functionalities such as replay of these collaboration events. The evaluation shows hundreds of kilobytes can be enough to store the events in a collaboration session for accurate replays, compared with hundreds of megabytes of Google Hangouts.

Gate sizing is one of the most important techniques for circuit optimization. Over the years, Elmore delay model (EDM) has been the predominant timing model used in gate sizing due to its simplicity. However, EDM is no longer effective in meeting the increasing demand of timing accuracy. In this paper, we propose a new gate delay model, which characterizes the timing information of lookup tables and creates a model which is mathematically similar to EDM, and can be easily incorporated into well-known EDM based gate sizing techniques using Lagrangian Relaxation (LR) with minor modifications. Experimental data show that it can produce even better results than those directly based on lookup tables, while keeping the benefit of the simplicity of EDM.

Complex timing constraints that refer to multiple clocks and/or edges are often used in the design of modern high performance processors. Such constraints complicate the design of downstream algorithms such as logic synthesis. The complexity of the overall CAD system can be reduced considerably if we can optimally transform the timing constraints so that they refer only to a single clock and edge. In this paper, we show how to model these multi clock/edge timing constraints and describe algorithms to reduce the number reference clocks/edges. We address the important problems of accurately handling signal transitions, sequential elements, input slope variations and timing overrides, which have not been addressed before.

Transistor reordering has been known to be effective in reducing delays of a circuit with nearly zero penalties. However, techniques to determine good transistor orders have not been proposed in literature. Previous work on this has to resort to running SPICE for all meaningful transistor orders and selecting a best one, which is extremely time-consuming. This paper proposes an efficient and accurate technique for determining best transistor orders without running SPICE simulations. Experimental results from SPICE3 show that the predictions are very accurate.

Accurate estimation of gate delays is essential for timing-related CAD tools. CAD researchers tend to use Elmore delay model for estimating gate delays. Since Elmore delay model was primarily developed for estimating interconnection delay, when applied to gate delay estimation, there will be significant inaccuracy. In this paper, by embedding concepts of electronic theories into switch-level analysis, a simple and efficient delay model for gates of general types (such as NAND, NOR, and complex gates) is proposed. Experimental data show that the proposed gate delay model consistently achieves high accuracy (typically within around 2% of SPICE simulations).

The use of multiple clocks has become a common practice in modern microprocessor design. With multiple clocks, the timing specifications have become complicated and tend to go beyond the ability of single-clock based CAD tools. This paper first introduces the concept of timing specification transformation. Then, this paper describes algorithms for transforming an interface timing specification with multiple clocks/edges into an equivalent specification with a single clock/edge for combinational circuit blocks. It formulates a new optimization problem, which is important but has never been addressed by CAD researchers. It identifies conditions under which this transformation can be performed efficiently without any loss of timing budget. The algorithm can be used to simplify the constraints to drive many synthesis and optimization algorithms.

In all stages of VLSI chip design, routing estimation is required to account for the effect of interconnects. We propose a fast Steiner tree construction algorithm, which is 3-180 times faster for 10-300 point Steiner trees, and within 2.5% of the length of the Batched-1-Steiner tree. The proposed method can be used as a fast net length estimation tool in VLSI CAD applications, e.g. in the inner cycle of a floorplanning/placement engine.

This paper presents a new timing driven placement algorithm that explicitly meets physical net lengths constraints. It is the first recursive bi-section placement (RBP) algorithm that meets precise half perimeter bounding box constraints on critical nets. At each level of the recursive bi-section, we use linear programming to ensure that all net constraints are met. Our method can easily be incorporated with existing RBP methods. We use the net constraint based placer to improve timing results by setting and meeting constraints on timing critical nets. We report significantly better timing results on each of the MCNC benchmarks and achieve an average optimization exploitation of 69% versus previously reported 53%.

We present a new timing driven method for global placement. Our method is based on the observation that similar net length reductions in the different nets that make up a path may not impact the path delay in the same way. For each net in the design, we compute the net sensitivity, or the path delay reduction as a result of net length improvements. We use very accurate delay models that include the impact of waveform slope and driver loading effects. Our new timing driven algorithm uses the sensitivity information to focus on nets that have the greatest impact on improving the worst circuit paths. Our method significantly improves the worst path delay over existing published work on industry circuits.

We present a novel global routing and cross-point assignment methodology for sea-of-gates (SOG) designs. Using the proposed congestion driven spanning trees (CDST), and continuously analyzing the congestion at all steps, nets are incrementally globally routed in one of the six well thought of heuristic steps of our methodology. This eliminates the need for rip-up and re-route and enables our approach to achieve good completion rates. We tested our flow on a number of testcases from the industry. The net lengths produced by our flow were compared to the theoretical lower-bound (steiner tree) and were found to be at most 4% worse. We compared the results of creating the net segments by the classical MST verses the CDST and observed an 80% improvement in the number of incomplete nets. Completing the detailed routing using a commercially available detailed router validated the results of the proposed global routing and cross-point assignment.

This paper proposes an approach for integrating CPU/disk/network scheduling and memory management for supporting a variety of VCR operations and dynamic service changes efficiently. Under this approach we can optimize individual resources, and support a maximal number of clients on a given system. We present a framework of service modeling to characterize the requested video services and identify the scheduling parameters for supporting these services. A number of techniques and methodologies are developed for analyzing the behaviors of disk accesses, network operations, and CPU activities under the loads of both single and multiple clients. We also describe an admission control strategy that utilizes information about all the system resources to determine if a set of video services is acceptable.

The transport of compressed video without loss of picture quality requires the network to support large fluctuations in bandwidth requirements. This paper introduces a lossless smoothing algorithm designed to satisfy any given set of buffer and delay constraints for both stored and live video applications with the goal of minimizing the number of rate changes and maximum rate. The algorithm is shown to be effective in smoothing bursty bit streams as illustrated by the experimental demonstration of MPEG encoded video.

A technique for chaining the transistors in the layouts of static CMOS leaf cells is presented and analyzed. This new method is superior to existing techniques, since it can operate on a more general class of circuits and is very efficient. It is shown that the layout width of a CMOS leaf cell can be significantly reduced (nearly 40% in the average case) by transistor chaining. Moreover, more than half of the switching functions of four variables have optimal CMOS circuit implementations with non-series/parallel topologies. Therefore, the use of non-series/parallel circuits can have a positive global impact on layout area and performance. The transistor chaining technique presented in this paper produces the optimal solution for 82% of the circuits tested, and has linear time complexity.

An important work related to the synthesis of asynchronous circuits from a signal transition graph (STG) specification is studied in this paper. The work is to test the satisfaction of one-token restriction. The one-token restriction is essential for an STG to avoid possible ambiguity in a behavioral specification. A graph reduction method which uses five reduction operations: series, parallel, unique-cycle, group-collapse, and conflict-block reductions, is proposed to achieve the task. Experimental results show that our proposed techniques are also very efficient for STGs of very large sizes.

A plane multigraph is said to be dual Eulerian if both it and its dual contain an Euler path or circuit and the Euler paths have corresponding edge sequences. In this paper several properties of plane multigraphs are derived, and a necessary and sufficient condition for a plane multigraph to be dual Eulerian is given. Although the necessary and sufficient condition for a multigraph to be Eulerian is somewhat trivial, the necessary and sufficient condition for a plane multigraph to be dual Eulerian is not. Nevertheless, the question of whether or not a plane multigraph is dual Eulerian can be answered in time proportional to a linear function of the number of edges of the graph, and an algorithm that answers this question is presented in this paper. This theory can be applied to the layout synthesis of functional cells for Complementary Metal-Oxide Semiconductor Very Large-Scale Integrated circuits.

In standard cell design, many cell terminals and gates are permutable, and it is important for a channel router to take advantage of this to obtain better results. An efficient hierarchical algorithm is presented to determine the proper positions of permutable gates and cell terminals such that the results of the subsequent channel routing can be significantly improved. Experimental results show that our proposed algorithm considerably reduces the number of tracks and vias, and its time complexity is linear in the number of cell terminals.>

In standard cell design, some of the cell terminals and gates are permutable. Therefore, it is important for an over-the-cell channel router to take advantage of this so as to obtain better results. A greedy algorithm is presented to determine proper gate and terminal positions such that, when over-the-cell routers are used, the area above and below the channel can be utilized more effectively and the maximal channel density can be greatly reduced. Experimental results show that our proposed algorithm indeed considerably reduces the maximal channel density.>

A CAD tool, LILA, that generates layouts of both one-dimensional and two-dimensional iterative logic arrays, described in VHDL or schematic structures, is presented. Such a tool is very important because in current industry, the generation of high density iterative logic arrays (such as data paths in microprocessors) is still mainly performed manually, and is a major bottleneck of the design. In LILA, interconnections between modules (i.e., cells) of the array do not need to be between adjacent modules and functions of modules of the array do not need to be identical. Regularity in module functions and interconnections between modules are automatically extracted by the tool. Based on interconnection wire length between modules, layouts of modules and interconnections are optimized in a single step. The signals in each array module are generated in such a way that signals in adjacent modules are perfectly aligned and connected by module abutments. As no global routing or channel routing between modules are necessary, the total layout area and propagation delay between modules are minimal. The proposed system is especially useful for data path modules, bit-level systolic arrays, storage devices, and many other regular structures, and has been actually implemented in a design environment. Extensive experiments have shown that the system has a very good performance and produces layouts of very high density. The tool takes about 1.6 CPU seconds to generate an eight-by-eight array divider on a SUN SPARCstation II.>

Patel (1981) proposed a probabilistic approach to analyze the performance of synchronous multistage interconnection networks (MINs) based on a uniform reference model and the assumption of independent requests. Patel's model and analytical results have been widely adopted by numerous researchers as a basis to investigate various aspects of MINs. We study in detail the effects of the independence assumption on the accuracy of system performance and point out the factors which cause an inaccuracy. A new queueing model is then proposed and is shown to be very accurate. Since only six states are needed, independent of the size of MINs, this new model is very efficient computationally.

A queueing model for the DQDB protocol with a single priority level is presented and analyzed. The state of a node is defined by the number of requests in the distributed queue prior to, and post generation of a segment. It is shown that the number of states that a node can be in, is finite and position dependent. Moreover, it is shown that the request rate and the network traffic that a node perceives at any particular moment are highly dependent on its state. An iterative technique is presented to calculate the request rate and network traffic for all the nodes in a DQDB network by carefully modeling the relationship between adjacent nodes. The node average waiting time and average throughput are analyzed as functions of the node position and state in the network. Our results illustrate the effect of the various parameters on the waiting time and throughput. Comparisons with simulation and existing analytical results are presented.

Abstract- In many applications, especially signal processing and matrix computations, algorithms are in a highly regular iterative form; access patterns for most variables are highly regular and uniform. Instead of always storing the values of variables back to and retrieving them from memory or register files, it will be much more efficient and cost effective to let those variables intelligently “stay ” or “flow ” in the data path for future use. In this paper, low cost and simple structured sequencers which are best exemplified by hardware stacks and queues are introduced in the data path for efficiently implementing such a novel concept. Various algorithms are developed to map variables to sequencers and to integrate sequencers into conventional high-level synthesis procedures. Experimental results show very encouraging improvement in the performance of designs as well as significant reduction in hardware cost. I.

This paper presents an algorithm to route multiple nets for VLSI layout synthesis in the presence of irregular rectilinear obstacles. The proposed routing algorithms are to be used when layout is nearly finished. Any incremental routing for performance needs to be done by using the very limited space between existing layout cells or by routing directly over the cells. Each net has multiple pins, which are located either on the boundary or anywhere inside the layout region. The proposed algorithm is very systematic and easy to implement. It does not require any net sequencing, and through extensive experiments on real circuits has been shown to always produce near optimal solutions.>

An efficient algorithm for searching for functional cells based on Boolean matching in a large library is presented. Redundant variables and permutation of inputs are considered in this algorithm. The algorithm does a search in constant time, independent of the size of the library.>

New algorithms are proposed to route multiple points for VLSI layout synthesis in the presence of irregular rectilinear obstacles. The proposed routing algorithms are to be used when layout is nearly complete, such that routing needs to be done by using very limited space between existing layout cells or by routing directly over the cells. A point-to-point routing algorithm is proposed. Which allows more general conditions, including point-to-path routing, over-the-cell routing, multi-layer routing and user guided routing. Then, the point-to-point routing algorithm is generalized to perform multi-point routing. Through benchmarks, we have found that the results of the router either match or outperform those generated by existing algorithms, using significantly fewer search lines.>

We present an efficient method for the performance evaluation of HIPPI interconnection system implementing a camp-on strategy. The camp-on feature has been defined in the HIPPI standards and implemented in switching designs but no performance analysis results have been published to the best of our knowledge. We model the system with only a fixed number of states. This reduction in the size of the state space has a direct impact on the computational time required. Our new models allow us to analyze the system not only with uniform traffic, but with many other different traffic patterns including uniform traffic, hot-spot traffic, general traffic pattern, locality of reference, etc. Moreover, we compare the performance of the camp-on and drop strategies and demonstrate that the camp-on outperforms the drop strategy.>

It has been pointed out that, in many cases, results generated by non-Manhattan channel routers will be better than those generated by Manhattan routers. Non-optimal bubble sort based algorithms for non-Manhattan channel routing have been proposed in the literature by also allowing connections in the +45/spl deg/ and /spl minus/45/spl deg/ directions. In this paper, optimal algorithms are proposed for the two-layer and three-layer non-Manhattan channel routing problems based on an identical problem formulation. The time complexities of our algorithms and the existing algorithm (which produces the best results so far) are O(K/sup 2/ * N) and O(K * N/sup 2/), respectively, where N is the number of terminals (i.e., the length) of the channel and N is the number of routing tracks (i.e., the height) in the channel. K is always less than N, and in most cases is much smaller than N. Clearly, a significant improvement in time complexity over the existing algorithm (which produces the best results so far) is achieved, while ensuring optimality.>

A new model for the performance evaluation of single-buffered multistage interconnection networks (MINs) is proposed. Previous models proposed in solving this problem are either not accurate enough or only applicable to a special case where the switching elements (SEs) are 2/spl times/2 crossbars. This new model allows the analysis of a MIN with SEs of arbitrary sizes (i.e., a/spl times/a) and, through extensive simulations, has been shown to be very accurate. Since only three states are required at each stage of a MIN, this model is efficient computationally.>

This paper presents a finite state analytical model and supporting simulation for performance analysis of a partially blocking, packet-switched, multistage communication network whose crossbar switches are output queued, non-lossy, and have an internal bandwidth (BW) such that 1/spl les/BW/spl les/a, where a is the number of inputs to the crossbar. To the knowledge of the authors, this is the only analytical model in the current literature that addresses this problem without making at least one of the following simplifying assumptions: (1) infinite number of inputs, (2) infinite number of buffers, (3) BW=a, (4) use of only a single crossbar (as opposed to multiple stages). The analytical model presented herein gives a set of closed-form equations which lead to an iterative solution for normalized bandwidth and normalized delay. The model provides results which are quite accurate (as shown by simulation) over a large range of parameter values (e.g., crossbar size, number of buffers in each queue, etc).>

The improvements in disk speeds have not kept up with improvements in processor and memory speeds. Conventional storage techniques, in the face of multimedia data, are inefficient and/or inadequate. Here, an efficient multimedia object allocation strategy is presented. We describe a multimedia object model, the object and storage device characteristics, and the fragmentation strategy. A bipartite graph approach is used for mapping fragments to storage devices and a cost function is used to determine an efficient allocation of an object and to balance the loads on the devices.>

A method which uses transistor reordering for the performance enhancement of CMOS circuits is presented.The proposed technique achieves significant reduction in propagation delays with little effect on layout area.The technique can be coupled with transistor sizing to achieve unbounded inlprovement in circuit delay, and it can be used to decrease dynamic power dissipation.In particular, excellent results have been achieved when the n~ethod is applied to data path circuits.I

The Markov-Modulated Bernoulli Process (MMBP) model is used to analyze the delay experienced by messages in clocked, packed-switched Banyan networks with k x k output-buffered switches. This approach allows us to analyze both single packet messages and multipacket messages with general traffic pattern including uniform traffic, hot-spot traffic, locality of reference, etc. The ability to analyze multipacket messages is very important for multimedia applications. Previous work, which is only applicable to restricted message and traffic patterns, resorts to either heuristic correction factors to artificially tune the model or tedious computational efforts. In contrast, the proposed model, which is applicable to much more general message and traffic patterns, not only is an application of a theoretically complete model but also requires a minimal amount of computational effort. In all cases, the analytical results are compared with results obtained by simulation and are shown to be very accurate.

Communication between processors is one of the most important issues in parallel and distributed systems. The authors study the communication aspects of a well known multiprocessor structure, the cube-connected cycles (CCC). Only nonoptimal routing algorithms and bounds on the diameter of restricted subclasses of the CCC have been presented in earlier work. The authors present an optimal routing algorithm for the general CCC, with a formal proof of its optimality. Based on this routing algorithm, they derive the exact network diameter for the general CCC.>

Recently there has been a trend for the designer to group registers into register files for efficiently implementing large VLSI chips. Multiport memories provide an effective way for such an implementation. Interconnection minimization (such as multiplexers and tristate buffers) has become more difficult with the use of multiport memories. A heuristic is presented which performs functional units and connection allocation tasks simultaneously to get better results for application specific designs assuming that registers have already been grouped to multiport memories. Experiments on benchmarks show very promising results.>

The authors provide an overall assessment of the current state-of-the art in multimedia information technology, the future directions and the engineering challenges faced by the designers and researchers working in this area. They describe how the newly emerging networking and high performance storage technologies can provide unique opportunities for building interesting multimedia applications, which were unconceivable previously.>

We present a model, based on a network of DX/D/1 queues, to predict the communication performance of static interconnection networks under various communication patterns. Our model predicts delay time distributions in the links as well as the first and second moments of the overall delay time of messages in the system. These predictions are verified by the results of simulations.

Gate matrix is a style which allows random logic layout to be performed in a regular manner. An algorithm is introduced which uses logic equations to determine a gate sequence and a set of nets which optimize the layout area. Using logic equations allows the reordering of transistors in a completely general manner. Previous work which uses dynamic net list and the concept of delayed binding performs only a small subset of the reordering possible with the proposed algorithm. The proposed algorithm uses a net-list-independent technique to determine the gate sequence. An optimized net list is created after the gate sequence is known. The algorithm has a time complexity of O(E log E) for a design with E logic equations. The experimental results show a considerable reduction in layout area.>

The performance evaluation of processor-memory communications for multiprocessor systems using circuit switched interconnection networks with a hold strategy is performed. Message size and processor processing time are considered and shown to have a significant effect on the overall system performance. A closed queuing network model is proposed such that only (n+2) states are required by the proposed model, in contrast to (n/sup 2/+3n+4)/2 states needed in previous studies, where n is the number of stages of the multistage interconnection network. Since a closed-form solution is obtained, the behavior of a complete cycle of memory access through multistage interconnection networks can be accurately analyzed and various performance bounds can be obtained.>

In thk paper a novel approach is presented to schedule iterative tasks on two-level pipelines under resource constraints, such that the executions of both high level iterations and low level operations are pipelined.Firs4 we limit the discussion to the case where none of the functional units is pipelined and pipelining is performed only at the global iteration level.Then we generalize it to the case where both global iterations and functional units are pipelined.We present the problem as an integer linear programming formulation and obtain the best solution which miniiizes the total execution time.Experimental resuhs show that the proposed algorithm produces optimal solutions for all the test cases we have tried within a few sewnds.

A novel design methodology for data path synthesis using multiport memories is presented which can be applied to scheduled algorithms or to already synthesized data paths as a postprocessor to reduce the design space. Based on simple and clear but powerful principles, the proposed technique not only groups variables to a minimum number of multiport memories depending on their ports and taking into consideration the variables' access requirements, but also minimizes their interconnection hardware (such as buses, multiplexers, and tri-state buffers) to functional units. The system, MAP, supports the synthesis of architecture in both linear topology and random topology for the application-specific design. The minimization problems have been formulated as 0-1 integer linear programming problems. Experiments on benchmarks show very promising results and the CPU time for all the benchmarks is less than 1.4 s.>

A hierarchical pin permutation algorithm is presented which is used as a preprocessor of conventional channel routing algorithms. This algorithm determines the proper positions of permutable gates and cell terminals such that the results of the subsequent channel routing can be significantly improved. First, gates and terminals are interchanged to maximize the number of aligned terminal pairs and to reduce the channel density. Then, terminals that are not aligned are interchanged to remove cyclic constraints in the vertical constraint graph (VCG). Experimental results show that the proposed algorithm considerably reduces the number of tracks and vias.>

Many optimization algorithms have been proposed for layout styles which are dual dependent: that is, the optimization for the layout of the n-transistor network of a CMOS complex gate is dependent on, the p-transistor network and vice versa. A two-stage linear-time optimization algorithm for dual independent layout styles is presented. The first stage is based on a tree representation of the complex gate. This tree representation allows complete flexibility in transistor order and takes complete advantage of the concept of delayed binding. The optimization goal is identical to the Euler pathed optimization algorithms metal-metal matrix (M/sup 3/) layout style, and examples of generated layouts are shown. Starting from a switching expression, the proposed algorithm always produces an optimal solution in terms of the number of diffusion breaks, which includes an optimal transistor representation for the switching expression (first stage), and an optimal gate sequence to traverse this transistor circuit (second stage).>

A systematic methodology based on the concept of delay distribution to optimize the systolic scheduling of data flow graphs, which represent one-dimensional linear recurrence algorithms (LRAs) is introduced. Step-by-step examples are given to illustrate the procedure. It is shown that this procedure produces optimally scheduled data flow graphs (DFGs) for VLSI systolic implementation. The goal is to transform the DFG of a linear recurrence algorithm into an optimal form for VLSI systolic implementation. Considerable improvements have been achieved over previous works. Comparisons are made between the authors' and previous designs on the examples of infinite impulse response (IIR) filters and finite impulse response (FIR) filters. Finally, a generalization of the procedure to N-dimensional linear recurrence algorithms is given, using the one-dimensional case as its basis.>

An algorithm is introduced which uses logic equations to determine a gate sequence and a set of nets which optimize the gate matrix layout area. Using logic equations allows the reordering of transistors in a completely general manner. Previous works using net-lists and the concept of delayed binding performed only a small subset of the reordering possible with the proposed algorithm. The algorithm has a time complexity of O(E log E) for a design with E equations. The experimental results show a considerable reduction in layout area. >

A class of (2n-1)-stage rearrangeable multistage interconnection networks (MINs) that includes all the previously proposed 2n-1 stage MINs as special cases or subsets is proposed. Both permutation routing and generalized distributed tag routing algorithms of this class of MINs are proposed. It is shown that previously proposed routing algorithms for some specific rearrangeable networks are just special cases of the general routing algorithm.>

Efficient algorithms for CMOS gate matrix layouts which have fully utilized the duality between NMOS and PMOS are presented. Improper assumptions made by previous authors are pointed out. Problems which have prevented previous algorithms from reaching a real optimal result are discussed and solved. Significant improvements are achieved over previous algorithms.>

Efficient algorithms for the layout generation of CMOS complex gates are presented. Heuristics which use the concept of delayed binding are introduced. An optimized net list is decided during the layout generation phase, rather than before. Examples are given showing that this approach can achieve a considerable improvement over previous ones.>