This paper proposes "path mapping," a method of delay estimation for technology independent combinational circuits. Path mapping provides fast and accurate delay estimation using common ideas with the tree covering based technology mapping. First, path mapping does technology mapping for all paths in the circuit with minimum mapped delay. Then, it finds the largest mapped delay among all the paths in the circuit, and answers it as an estimated circuit delay. Experimental results show path mapping estimates more accurate circuit delay than unit delay, and runs much faster than the technology mapping.
Jian YANG Yoshio YAMAGUCHI Hiroyoshi YAMADA Shiming LIN
For the completely polarized wave case, this paper presents the explicit formulae of the characteristic polarization states in the co-polarized radar channel, from which one can obtain the CO-POL Max, the CO-POL Saddle and the CO-POL Nulls in the Stokes vector form. Then the problem on the polarimetric contrast optimization is discussed, and the explicit formula of the optimal polarization state for contrast enhancement is presented in the Stokes vector form for the first time. To verify these formulae, we give some numerical examples. The results are completely identical with other authors', which shows the validity of the presented method.
Edoardo CHARBON Enrico MALAVASI Paolo MILIOZZI Alberto SANGIOVANNI-VINCENTELLI
In this paper we propose a comprehensive approach to physical design based on the constraint paradigm. Bounds on the most critical circuit parasitics are automatically generated to help designers and/or physical design tools meet a set of high-level specifications. The constraint generation engine is based on constrained optimization, where various parasitic effects on interconnect and devices are accounted for and dealt with in different manners according to their statistical behavior and their effect on performance.
Katsuharu SUZUKI Nozomu TOGAWA Masao SATO Tatsuo OHTSUKI
Entropy coding/decoding are implemented on FPGAs as a fast and flexible system in which high-level synthesis technologies are key issues. In this paper, we propose scheduling and allocation algorithms for behavioral descriptions of entropy CODEC. The scheduling algorithm employs a control-flow graph as input and finds a solution with minimal hardware cost and execution time by merging nodes in the control-flow graph. The allocation algorithm assigns operations to operators with various bit lengths. As a result, register-transfer level descriptions are efficiently obtained from behavioral descriptions of entropy CODEC with complicated control flow and variable bit lengths. Experimental results demonstrate that our algorithms synthesize the same circuits as manually designed within one second.
Yoshio YAMAGUCHI Masafumi NAKAMURA Hiroyoshi YAMADA
One of the polarimetric radar applications is classification or identification of targets making use of the scattering matrix. This paper presents a decomposition scheme of a scattering matrix into three elementary scattering matrices in the circular polarization basis. The elementary components are a sphere, a diplane (dihedral corner reflector), and a helix. Since a synthetic aperture FM-CW radar provides scattering matrix through a polarimetric measurement, this decomposition scheme was applied to the actual raw data, although the matrix is resulted from a swept frequency measurement. Radar imaging experiments at the Ku band (14.5-15.5GHz) were carried out to obtain a total of 6464 scattering matrices in an imaging plane, using flat plates, corner reflectors and wires as elementary radar targets for classification. It is shown that the decomposition scheme has been successfully carried out to distinguish these targets and that the determination of rotation angle of line target is possible if the scattering matrix is classified as a wire.
Haruhisa HASEGAWA Naoaki YAMANAKA Kohei SHIOMOTO
A new adaptive rate control with congestion prediction is developed that is highly robust against long propagation delays. It minimizes the network performance degradation caused by the delay based on prediction by extrapolating past data and correction using new notification. The simulation results show that our proposed control maintains high throughput and a smaller buffer even in long propagation delay networks, like ATM-WAN.
Dror ROTTER Kiyoharu HAMAGUCHI Shin-ichi MINATO Shuzo YAJIMA
Minato has proposed canonical representation for polynomial functions using zero-suppressed binary decision diagrams (ZBDDs). In this paper, we extend binary moment diagrams (BMDs) proposed by Bryant and Chen to handle variables with degrees higher than l. The experimental results show that this approach is much more efficient than the previous ZBDDs' approach. The proposed approach is expected to be useful for various problems, in particular, for computer algebra.
Tsuyoshi ISSHIKI Wayne Wei-Ming DAI Hiroaki KUNIEDA
In this paper, we will show some significant results of the routability analysis of bit-serial pipeline datapath designs based on Rent's rule and Donath's observation. Our results show that all of the tested bit-serial benchmarks have Rent exponent of below 0.4, indicating that the average wiring length of the circuit is expected to be independent of the circuit size. This study provides some important implications on the silicon utilization and time-area efficiency of bit-serial pipeline circuits on FPGAs and ASICs.
Sung-Won LEE Dong-Ho CHO Yeong-Jin KIM Sun-Bae LIM
In this paper, we consider conventional signaling link fault tolerance and error correction mechanisms to provide reliable services of mobile multimedia telecommunication network based on ATM (Asynchronous Transfer Mode) technology. Also, we propose an efficient signaling protocol interworking architecture and a reliable distributed interworking network architecture between SS7 based FPLMTS and ATM networks. Besides, we evaluate the performance of proposed method through computer simulation. According to the results, proposed signaling architecture shows efficient and fast fault restoration characteristics than conventional MTP-3/3b based network. Functional signaling protocol stack and network architecture of proposed fast rerouting mechanism provide reliable and efficient restoration performance in view of interworking between SS7 based FPLMTS and ATM networks.
Ricardo FERREIRA Anne-Marie TRULLEMANS Qinhai ZHANG
We present here the Controlling Value Boolean Matching based on fault analysis. The problem is to match a Boolean function with don't cares on library cells under arbitrary input permutations and/or input-output phase assignments. Most of the library cells can be represented by tree structure circuits. The approach presented here is suitable for these structures and computes the Boolean matching better than the structural matching used in SIS. It can handle library cells with a general topology and reconvergent paths. The benchmark test shows that the Controlling Value Boolean Matching can be as facter as the structural matching used in SIS.
Shunji SAIKA Masahiro FUKUI Noriko SHINOMIYA Toshiro AKINO Shigeo KUNINOBU
We propose a transistor placement algorithm to generate standard cell layout in a two-dimensional placement style. The algorithm optimizes the one-dimensional placement in the first stage, folds the large transistors in the second stage, and optimizes the two-dimensional placement in the final stage. We also propose "cost function" based on wiring length, which closely match the cell optimization. This transistor placement algorithm has been applied to several standard cells, and demonstrated the capability to generate a two-dimensional placement that is comparable to manually designed placement.
Tadashi DOHI Takashi AOKI Naoto KAIO Shunji OSAKI
This paper considers a probabilistic model for a database recovery action with checkpoint generations when system failures occur according to a renewal process whose renewal density depends on the cumulative operation period since the last checkpoint. Necessary and sufficient conditions on the existence of the optimal checkpoint interval which maximizes the ergodic availability are analytically derived, and solvable examples are given for the well-known failure time distributions. Further, several methods to be needed for numerical calculations are proposed when the information on system failures is not sufficient. We use four analytical/tractable approximation methods to calculate the optimal checkpoint schedule. Finally, it is shown through numerical comparisons that the gamma approximation method is the best to seek the approximate solution precisely.
We have previously proposed a scannable memory configuration which is useful in testing logic blocks around memory arrays. Although the configuration is supposed to be effective in testing the memory array itself by its frequent read/write access during the scan operation, it has not been theoretically shown what types of faults can be detected. In this paper, from a viewpoint of memory testing, we investigate the testability of the scannable memory configuration and propose a memory array test using the scan path. It is shown that we can detect (1) all stuck-at faults in memory cells, (2) all stuck-at faults in address decoders, (3) all stuck-at faults in read/write logic, (4) static, dynamic and 2-coupling faults between memory cells of adjacent words, and (5) static coupling faults between memory cells in the same word. The test can be accomplished simply by comparing scan-in data and scan-out data. The test vector is 20ms bit long, where m is the number of words of the memory array under test and s is the total scan path length.
Naoyuki ISO Yasushi KAWAGUCHI Tomio HIRATA
In VLSI and printed wiring board design, routing process usually consists of two stages: the global routing and the detailed routing. The routability checking is to decide whether the global wires can be transformed into the detailed ones or not. In this paper, we propose two graphs, the capacity checking graph and the initial flow graph, for efficient routability checking in planar layouts.
After analyzing the limitations of the traditional description of CMOS circuits at the gate level, this paper introduces the notions of switching and signal variables for describing the switching states of MOS transistors and signals in CMOS circuits, respectively. Two connection operations for describing the interaction between MOS transistors and signals and a new description for MOS circuits at the switch level are presented. This new description can be used to express the functional relationship between inputs and the output at the switch level. It can also be used to describe the circuit structure composed of MOS switches. The new description can be effectively used to design both CMOS circuits and nMOS pass transistor circuits.
Mika ISHIZUKA Arata KOIKE Masatoshi KAWARASAKI
This paper evaluates the performance of TCP over ATM by simulation studies to clarify its applicability to high-speed WANs. We compared the performance of TCP over ABR with that of TCP over UBR, and TCP over UBR with Early Packet Discard (EPD). As for TCP over UBR, TCP has all responsibilities for end-to-end performance. In this case, cell loss at the ATM layer degrades TCP performance. Optimum tuning of TCP parameters may mitigate this degradation problem, but cannot solve it. Using EPD with UBR can fairly reduce useless transmission of corrupted packets and improve TCP performance, but still have the problem on fairness. As a result, TCP over ABR was proved to be the most effective as long as it suppressed cell loss. It was also proved that, if we want to extract best performance by TCP over ABR, we need to choose TCP parameters such as window size or timer granularity, so that ABR rate control does not interact with TCP window control and retransmission control.
Tsunemasa HAYASHI Atsushi TAKAHARA Kennosuke FUKAMI
This paper presents an FPGA architecture for high-speed systems, such as next-generation B-ISDN telecommunications systems. Such a system requires an LSI in which an over-10K-gate circuit can be implemented and that has a clock cycle rate of 80MHz. So far, the FPGA architecture has only been discussed in terms of its circuit structure. In contrast we consider the circuit structure of the FPGA along with the performance of its dedicated CAD system. We evaluate several FPGA logic-element structures with a technology mapping method. From these experiments, a multiplexor-based logic-element is found to be suitable for implementing such a high-speed circuit using the BDD-based technology mapping method. In addition, we examine how to best utilize the characteristics of the selected logic-cell structure in designing the wiring structure. It is found that the multiplexor-based cell can be connected efficiently in a clustered wiring structure.
Dirk STROOBANDT Jan VAN CAMPENHOUT
In computer hardware there is a constant evolution towards smaller transistor sizes. At the same time, more and more transistors are placed on one chip. Both trends make the pin limitation problem worse. Scaling down chip sizes adds to the shortage of available pins while increasing the number of transistors per chip imposes a higher need for chip terminals. The use of three-dimensional systems would alleviate this pin limitation problem. In order to decide whether the benefits of such systems balance the higher processing costs, one must be able to characterize these benefits accurately. This can be done by estimating important layout properties of electronic designs, such as space requirements and interconnection length values. For a two-dimensional placement, Donath found an upper bound for the average interconnection length that follows the trends of experimentally obtained average lengths. Yet, this upper bound deviates from the experimentally obtained value by a factor of approximately 2 which is not sufficiently accurate for some applications. In this paper, we first extend Donath's technique to a three-dimensional placement. We then compute a significantly more accurate estimate by taking into account the inherent features of the optimal placement process.
Yoshio KOBAYASHI Hiromichi YOSHIKAWA Seiichiro ONO
It is shown that a three-fluid model, which was successfully introduced to explain microwave characteristics of high-Tc superconductors phenomenologically, is suit also to explain those of low-Tc superconductors. In this model, the two contributions of a residual normal electron, in addition to a super and a normal electron in the two-fluid model, and of the temperature (T) dependence of momentum relaxation time τ for the two normal electrons are taken into account. Measured results of the T dependence of surface resistance Rs for a Nb film with critical temperature Tc9.2K agree very well with an Rs curve calculated using the present model, where a residual surface resistance at T0K, Rso, and the T dependence of τ were determined using the surface reactance at 0K Xso37.6mΩ calculated using the BCS theory to fit a calculated Rs curve with the measured values as a function of T. Furthermore, microwave characteristics predicted from the BCS theory cannot be explained phenomenologically using the conventional two-fluid model. This difficulty can be solved by using an improved two-fluid model, called the two-fluid (τ) model, where the T dependence of τ is taken into account. Finally the frequency dependence of Rs calculated for the Nb film is f1.9 for the BCS theory and f2.0 for the three-fluid (τ) model on the assumption of the frequency independence of τ.
As the global telecommunications industry moves into the next millennium, the difficulty, the frequency and the importance of interworking will increase due to three factors. First, as the last decade has shown, new technology is being created and deployed at an ever increasing rate and with higher complexity. This will result in greater difficulty to successfully interwork between technologies. Secondly, because competition has led to an increase in the number of carriers providing services, there will be more and more instances of interworking among carriers. Lastly, because all the carriers are hoping to be profitable, the interworking needs to be fast and easy to implement, have low costs and be seamless for users. Otherwise, increased costs and low customer satisfaction will reduce profits and possibly drive the carrier out of business. This paper will examine these assertions and discuss trends which support this proposition.