Masakazu AOKI Shin-ichi OHKAWA Hiroo MASUDA
We propose guidelines for LSI-chip design, taking the within-die variations into consideration, and for process quality improvement to suppress the variations. The auto-correlation length, λ, of device variation is shown to be a useful measure to treat the systematic variations in a chip. We may neglect the systematic variation in chips within the range of λ, while σ2 of the systematic variation must be added to σ2 of the random variation outside the λ. The random variations, on the other hand, exhibit complete randomness even in the closest pair transistors. The mismatch variations in transistor pairs were enhanced by 1.41(=) compared with the random variations in single transistors. This requires careful choice of gate size in designing a transistor pair with a minimum size, such as transfer gates in an SRAM cell. Poly-Si gate formation is estimated to be the most important process to ensure the spatial uniformity in transistor current and to enhance circuit performance. Large relative variations are observed for the contact to p+ diffusion, via1 (M1-M2), and via2 (M2-M3) among parameter variations in passive elements. The standard deviations for random variations in via1 and via2 are noticeably widespread, indicating the importance of the via resistance control in BEOL. The spatial frequency power spectrum for within-die random variations is confirmed experimentally, as uniform ('white') with respect to the spatial frequency. To treat the large 'white random noise,' the least-square method with a 4th-order polynomial exhibits a best efficiency as a fitting function for decomposing the raw variation data into systematic part and random part.
Yukio OGAWA Teruhiro HIRATA Kouji TAKAMURA Keiichi YAMAHA Satomu SAITOU Kouichi IWANAGA Tsutomu KOITA
We have developed an experimental approach that allows us to estimate the performance of a large-scale enterprise network to update routing information. This approach was applied to the integration of the UFJ Bank network system on January 15, 2002. The main characteristic of this approach is the application of a formula that represents the delays in updating routing information that accompany reductions in CPU resources. This procedure consists of two steps: one is to estimate the reduction in the availability of CPU resources caused by forwarding of data packets at a router, and the other is to estimate the levels of CPU resources required for replying to a query about a new route and subsequently updating the routing information. These steps were applied to estimate the performance of the network in terms of routing information convergence. The results of our experiments on the network showed that updating the routing information was possible as long as the average level of CPU utilization during any five-minute period at the routers was less than 40%. We were able to apply this guideline and thus confirm the stability of the UFJ Bank network.
In this paper, we propose a global routing method for 2-layer BGA packages. In our routing model, the global routing for each net is uniquely determined by a via assignment of each net. Our global routing method starts from an initial monotonic via assignment and incrementally improves the via assignment to optimize the total wire length and the wire congestion. Experimental results show that our proposed method generates a better global routing efficiently.
Hong-Hsu YEN FrankYeong-Sung LIN
An essential issue in designing, operating and managing a modern network is to assure end-to-end QoS from users perspective, and in the meantime to optimize a certain average performance objective from the systems perspective. So in the first part of this paper, we address the above issue by using the rerouting approach, where the objective is to minimize the average cross-network packet delay in virtual circuit networks with the consideration of an end-to-end delay constraint (DCR) for each O-D pair. The problem is formulated as a multicommodity network flow problem with integer routing decision variables, where additional end-to-end delay constraints are considered. As the traffic demands increases over time, the rerouting approach may not be applicable, which results in the necessity of capacity augmentation. Henceforth, the second part of this paper is to jointly consider the link capacity assignment and the routing problem (JCR) at the same time where the objective is to minimize the total link installation cost with considering the average and end-to-end delay constraints. Unlike previous research tackling this problem with a two-phase approach, we propose an integrated approach to considering the routing and capacity assignment at the same time. The difficulties of DCR and JCR result from the integrality nature and particularly the nonconvexity property associated with the end-to-end delay constraints. We propose novel Lagrangean relaxation based algorithms to solve the DCR and the JCR problems. Through computational experiments, we show that the proposed algorithms calculate near-optimal solutions for the DCR problem and outperform previous two-phase approach for the JCR problem under all tested cases.
Recently, the research on all-optical analog-to-digital conversion (ADC) has been extensively attempted to break through inherently limited operating speed of electronic devices. In this paper, we describe a novel quantization scheme by slicing supercontinuum (SC) spectrum for all-optical ADC and then propose a 2-bit all-optical ADC scheme consisting of the quantization by slicing SC spectrum and the coding by switching pulses with a nonlinear optical loop mirror (NOLM). The feasibility of the proposed quantization scheme was confirmed by numerical simulation. We conducted proof-of-principle experiments of optical quantization by slicing SC spectrum with an arrayed waveguide grating and optical coding by switching pulses with NOLM. We successfully demonstrated optical quantization and coding, which allows us to confirm the feasibility of the proposed 2-bit ADC scheme.
"Can one walk to infinity on Gaussian primes taking steps of bounded length?" We adopted computational techniques to probe into this open problem. We propose an efficient method to search for the farthest point reachable from the origin, which can be parallelized easily, and have confirmed the existence of a moat of width k =, whereas the best previous result was k = due to Gethner et al. The amount of computation needed for k = is about 5000 times larger than that for k =. A refinement of Vardi's estimate for the farthest distance reachable from the origin is proposed. The proposed estimate incorporates discreteness into Vardi's that is based on percolation theory.
Ryuji WAKIKAWA Carl WILLIAMS Keisuke UEHARA Jun MURAI
On the Internet, two different IP protocols are deployed such as IPv4 and IPv6. The Mobile Router uses the basic NEMO protocol which is IPv6 protocol specific. During the early period of time that IPv6 transition is occurring it is very likely that a Mobile Router will move to an IPv4 only access network. When this occurs the Mobile Router will no longer be able to operate using the basic NEMO protocol. There has already been some earlier work to provide IPv6 capability over an IPv4 access network for a Mobile Router. This paper provides a capability by to maintain IPv6 connectivity for the Mobile Router via its Home Agent with IPv4-in-IPv6 encapsulation with no special boxes to be deployed elsewhere in the network.
Global computing system (GCS) harnesses the idle CPU resources of clients connected to Internet for solving large problems that require high volume of computing power. Since GCS scale to millions of clients, many projects usually adopt coarse-grained scheduling in order to reduce server-side contention at the expense of sacrificing the degree of parallelism and wasting CPU resources. In this paper, we propose a new type of client, i.e., a scheduling proxy that enables adaptive-grained scheduling between the server and clients. While the server allocates coarse-grained work units to scheduling proxies alone, clients download fine-grained work units from a relatively nearby scheduling proxy not from the distant server. By computation of small work units at client side, the turnaround time of work unit can be reduced and the waste of CPU time by timeout can be minimized without increasing the performance cost of contention at the server. In addition, in order not to lose results in the failure of scheduling proxies, we suggest a technique of result caching in clients.
Hideaki OKAZAKI Katsuhide FUJITA Hirohiko HONDA Hideo NAKANO
This paper provides algorithms in order to solve an interval implicit function of the Poincare map generated by a continuous piece-wise linear (CPWL) vector field, with the use of interval arithmetic. The algorithms are implemented with the use of MATLAB and INTLAB. We present an application to verification of canards in two-dimensional CPWL vector field appearing in nonlinear piecewise linear circuits frequently, and confirm that the algorithms are effective.
Vasaka VISOOTTIVISETH Hiroyuki KIDO Katsuyoshi IIDA Youki KADOBAYASHI Suguru YAMAGUCHI
Although IP Multicast offers efficient data delivery for large group communications, the most critical issue delaying widespread deployment of IP Multicast is the scalability of multicast forwarding state as the number of multicast groups increases. Sender-Initiated Multicast (SIM) was proposed as an alternative multicast forwarding scheme for small group communications with incremental deployment capability. The key feature of SIM is in its Preset mode with the automatic SIM tunneling function, which maintaining forwarding information states only on the branching routers. To demonstrate how SIM increases scalability with respect to the number of groups, in this paper we evaluate the proposed protocol both through simulations and real experiments. As from the network operator's point of view, the bandwidth consumption, memory requirements on state-and-signaling per session in routers, and the processing overhead are considered as evaluation parameters. Finally, we investigated the strategies for incremental deployment.
Jittima NITTAYAWAN Suwan RUNGGERATIGUL
Several regular topologies have been proposed to be used as the logical topology for WDM networks. These topologies are usually evaluated and compared based on the metrics related to network performance. It can be simply shown that this is generally not sufficient since better network performance can be achieved by increasing more network facilities. However, doing this eventually increases the network cost. Thus, the comparison of topologies must be performed by using an evaluation function that includes both the network performance metric and the network cost. In this paper, we propose a model to find the optimum regular logical topology for wavelength routed WDM networks. ShuffleNet, de Bruijn graph, hypercube, Manhattan Street Network, and GEMNet are the five well-known and commonly used regular topologies compared in this paper. By solving the two subproblems on node placement optimization, and routing and wavelength assignment, we obtain the evaluation function used in the topology comparison. Numerical results show that GEMNet is the optimum logical topology for the wavelength routed WDM networks, where it can take one of the three forms of ShuffleNet, de Bruijn graph, and its own configurations.
BGP might experience a lengthy path exploration process to reach the convergence after the routing changes. found that the BGP rate-limiting timer--MinRouteAdvertisementInterval (MRAI) has an optimal value Mo that achieves the best trade-off between the stability and the convergence speed. In this paper, with the aid of a timed BGP model, we investigate the effects of MRAI and its optimal value Mo for the BGP convergence process. We find that an adequately long MRAI timer can batch-remove candidate paths and ensure the routing stability in the convergence process. There exists a minimal MRAI Ms that achieves the effect, which is also the upper bound of Mo and provides an approximation of Mo. We calculate the approximations of Ms for different settings and estimate the optimal MRAI for the Internet. According to the results, the optimal MRAI for the Internet might be 5-10 times less than the current default value used in the Internet. The simulations taken with SSFNet and the experiments conducted over the Planet-Lab demonstrate the correctness of our analysis.
Katsunori TANAKA Shigeru YAMASHITA Yahiko KAMBAYASHI
In this paper, we present the condition for the effective wire addition in Look-Up-Table-based (LUT-based) field programmable gate array (FPGA) circuits, and an optimization procedure utilizing the effective wire addition. Each wire has different characteristics, such as delay and power dissipation. Therefore, the replacement of one critical wire for the circuit performance with many non-critical ones, i.e., many-addition-for-one-removal (m-for-1) is sufficiently useful. However, the conventional logic optimization methods based on sets of pairs of functions to be distinguished (SPFDs) for LUT-based FPGA circuits do not make use of the m-for-1 manipulation, and perform only simple replacement and removal, i.e., the one-addition-for-one-removal (1-for-1) manipulation and the no-addition-for-one-removal (0-for-1) manipulation, respectively. Since each LUT can realize an arbitrary internal function with respect to a specified number of input variables, there is no sufficient condition at the logic design level for simple wire addition. Moreover, in general, simple addition of a wire has no effects for removal of another wire, and it is important to derive the condition for non-simple and effective wire addition. We found the SPFD-based condition that wire addition is likely to make another wire redundant or replaceable, and developed an optimization procedure utilizing this effective wire addition. According to the experimental results, when we focused on the delay reduction of LUT-based FPGA circuits, our method reduced the delay by 24.2% from the initial circuits, while the conventional SPFD-based logic optimization and the enhanced global rewiring reduced it by 14.2% and 18.0%, respectively. Thus, our method presented in this paper is sufficiently practical, and is expected to improve the circuit performance.
A diagnosis technique is presented to locate at least one fault in a scan chain with multiple timing faults. This diagnosis technique applies Single Excitation (SE) patterns of which only one bit can be flipped even in the presence of multiple faults. By applying the SE patterns, the problem of simulations with unknown values is eliminated. The diagnosis result is therefore deterministic, not probabilistic. Experiments on the ISCAS benchmark circuits show that the average diagnosis resolution is less than ten scan cells.
Recently, major services provided by mobile communications systems are shifting from voice conversations to data communications over the Internet. There is a strong demand for increasing the data transmission rate. However, an important problem arises; larger peak transmit power is required as transmission rate becomes higher. In this paper, we propose a wireless multi-hop virtual cellular concept to avoid this power problem. The virtual cellular network consists of a central port, which is a gateway to the network, and many distributed wireless ports. Transmit power and frequency efficiencies of the virtual cellular network are evaluated by computer simulation to compare with that of the present cellular networks. In the wireless multi-hop virtual cellular network, routing among wireless ports is an important technical issue. We propose a routing algorithm based on the total uplink transmit power minimization criterion and evaluate the total transmit power by computer simulation.
Katsunori MAKIHARA Yoshihiro OKAMOTO Hideki MURAKAMI Seiichiro HIGASHI Seiichi MIYAZAKI
Hydrogenated germanium films were fabricated in the thickness range of 7-98 nm on SiO2 at 150 by an rf glow discharge decomposition of 0.25% GeH4 diluted with H2, and the nucleation and growth of Ge nanocrystallites were measured from topographic and current images simultaneously taken by a conductive AFM probe after Cr contact formation on films so prepared. We have demonstrated that current images show fine grains in comparison with topographic images and the lateral evolution of the Ge grains with progressive film growth. The contrast in current images can be interpreted in terms of the difference in electron concentration between nanocrystalline grains and their boundaries.
Anycast refers to the transmission of data from a source node to (any) one member in the group of designed recipients in a network. When the physical network and the set of anycast requests are given, the WDM anycast routing problem (WARP) is to find a set of light-paths, one for each source, for anycasting messages to one of the member in the anycast destination group such that not any path using the same wavelength passes through the same link. The goal of the WARP is to minimize the number of used wavelengths. In this paper, the WARP is formulated and studied, since WARP is NP-hard, several heuristic algorithms and a hybrid method which combines heuristic and simulated annealing techniques are proposed to solve it. These algorithms are used to find the close-to-optimal solution. Simulated results show that the proposed algorithms are able to achieve good performance.
Fumio ARAKAWA Tomoichi HAYASHI Masakazu NISHIBORI
Parallel execution of the carry propagate adder (CPA) and leading non-zero (LNZ) detector that processes the CPA result is a common way to reduce the latencies of floating-point instructions. However, the conventional methods usually cause one-bit errors. We developed an exact LNZ detection circuit operating in parallel with the CPA. The circuit is implemented in the floating-point unit of our newly developed embedded processor core. Circuit simulation results show that the LNZ circuit has a similar speed to the CPA, and it contributes to make a small low-power FPU for an embedded processor core.
Taku SHIBAGUCHI Mitsuhisa IKEDA Hideki MURAKAMI Seiichi MIYAZAKI
We have fabricated Al-gate MOS capacitors with a Si quantum-dots (Si-QDs) floating gate, the number of dots was changed in the range of 1.6-4.81011 cm-2 in areal density with repeating the formation of Si dots and their surface oxidation a couple of times. The capacitance-voltage (C-V) characteristics of Si-QDs floating gate MOS capacitors on p-Si(100) confirm that, with increasing number of dots density, the flat-band voltage shift due to electron charging in Si-QDs is increased and the accumulation capacitance is decreased. Also, in the negative bias region beyond the flat-band condition, the voltage shift in the C-V curves due to the emission of valence electrons from intrinsic Si-QDs was observed with no hysterisis presumably because holes generated in Si-QDs can smoothly recombine with electrons tunneling through the 2.8 nm-thick bottom SiO2. In addition, we have demonstrated the charge retention characteristic improves in the Si-QDs stacked structure.
Peigang HU Yaohui JIN Weisheng HU Yikai SU Wei GUO Chunlei ZHANG Hao HE Weiqiang SUN
In this letter, we study dynamic multicasting in GMPLS networks with unequal branching capability. An overlapped multicasting tree is proposed to reduce blocking probability, which can utilize the branching capabilities more efficiently than the traditional Steiner tree. A nearest node branch first heuristic is developed to find such an overlapped tree.