An approximation algorithm composed of a digital neural network (DNN) and a modified greedy algorithm (MGA) is presented for the board-level routing problem (BLRP) in a logic emulation system based on field-programmable gate arrays (FPGA's) in this paper. For a rapid prototyping of large scale digital systems, multiple FPGA's provide an efficient logic emulation system, where signals or nets between design partitions embedded on different FPGA's are connected through crossbars. The goal of BLRP, known to be NP-complete in general, is to find a net assignment to crossbars subject to the constraint that all the terminals of any net must be connected through a single crossbar while the number of I/O pins designated for each crossbar m is limited in an FPGA. In the proposed combination algorithm, DNN is applied for m = 1 and MGA is for m 2 in order to achieve the high solution quality. The DNN for the N-net-M-crossbar BLRP consists of N M digital neurons of binary outputs and range-limited non-negative integer inputs with integer parameters. The MGA is modified from the algorithm by Lin et al. The performance is verified through massive simulations, where our algorithm drastically improves the routing capability over the latest greedy algorithms.

Rapid system prototyping is one of the main applications for field-programmable gate arrays (FPGAs). At the stage of rapid system prototyping, design specifications can often be changed since they cannot be determined completely. In this paper, layout design change is focused on and a layout reconfiguration algorithm is proposed for FPGAs. The target FPGA architecture is developed for transport processing. In order to implement more various circuits flexibly, it has three-input lookup tables (LUTs) as minimum logic cells. Since its logic granularity is finer than that of conventional FPGAs, it requires more routing resources to connect them and minimization of routing congestion is indispensable. In layout reconfiguration, the main problem is to add LUTs to initial layouts. Our algorithm consists of two steps: For given placement and global routing of LUTs, in Step 1 an added LUT is placed with allowing that the position of the added LUT may overlap that of a preplaced LUT; Then in Step 2 preplaced LUTs are moved to their adjacent positions so that the overlap of the LUT positions can be resolved. Global routes are updated corresponding to reconfiguration of placement. The algorithm keeps routing congestion small by evaluating global routes directly both in Steps 1 and 2. Especially in Step 2, if the minimum number of preplaced LUTs are moved to their adjacent positions, our algorithm minimizes routing congestion. Experimental results demonstrate that, if the number of added LUTs is at most 20% of the number of initial LUTs, our algorithm generates the reconfigured layouts whose routing congestion is as small as that obtained by executing a conventional placement and global routing algorithm. Run time of our algorithm is within approximately one second.

A floorplan is a partition of a rectangle into subrectangles, each of which is associated with a module. Zero-wasted-area layouts are known to exist when the height and width of modules are constrained only by the area, and several methods have been proposed for deriving such layouts. However, because these methods are global and indirect, they are inherently slow. We propose a new algorithm which simulates the air-pressure mechanics. It begins with a layout, which is not necessarily feasible, and iterates the movement of one wall at a time to the force-balancing position. The key issue is that it is guaranteed that every movement makes a current layout approach a zero-wasted-area layout by the measure of energy which is defined here. Experimental results on the example in several literatures and artificially made complex examples showed very fast convergence. The algorithm is evolved to methods which move all the walls simultaneously, resulting in a further speed enhancement.

This paper proposes a new design method of a nonlinear filtering algorithm in continuous-time stochastic systems. The observed value consists of nonlinearly modulated signal and additive white Gaussian observation noise. The filtering algorithm is designed based on the same idea as the extended Kalman filter is obtained from the recursive least-squares Kalman filter in linear continuous-time stochastic systems. The proposed filter necessitates the information of the autocovariance function of the signal, the variance of the observation noise, the nonlinear observation function and its differentiated one with respect to the signal. The proposed filter is compared in estimation accuracy with the MAP filter both theoretically and numerically.

Multi-recast techniques make it possible for a voter to participate in a sequence of different designated votings by using only one ticket. In a multi-recastable ticket scheme for electronic voting, every voter of a group can obtain an m-castable ticket (m-ticket), and through the m-ticket, the voter can participate in a sequence of m different designated votings held in this group. The m-ticket contains all possible intentions of the voter in the sequence of votings, and in each of the m votings, a voter casts his vote by just making appropriate modifications to his m-ticket. The authority cannot produce both the opposite version of a vote cast by a voter in one voting and the succeeding uncast votes of the voter. Only one round of registration action is required for a voter to request an m-ticket from the authority. Moreover, the size of such an m-ticket is not larger than that of an ordinary vote. It turns out that the proposed scheme greatly reduces the network traffic between the voters and the authority during the registration stages in a sequence of different votings, for example, the proposed method reduces the communication traffic by almost 80% for a sequence of 5 votings and by nearly 90% for a sequence of 10 votings.

Quality of service requirements are satisfied conjointly by the service model, which determines how resources are shared and by network engineering, which determines how much capacity is provided. In this paper we consider the impact of the adopted charging scheme on the feasibility of fulfilling QoS requirements. We identify three categories of charging scheme based respectively on flat rate pricing, congestion pricing and transaction pricing.

Media processors have emerged so that a single LSI can realize multiple multimedia functions, such as graphics, video, audio and telecommunication with effectively shared hardware and flexible software. First, the difference between media processors and general-purpose microprocessors with multimedia extensions is clarified. Features for processes and data in the multimedia applications are summarized and are followed by the multimedia enhancements that the recent general-purpose microprocessors use. The architecture for media processors reflects the further optimized utilization of these features and realizes better price-performance ratio than the general-purpose microprocessors. Finally, the future directions of media processors are estimated, based on the performance, the power dissipation and the die size of the present microprocessors with multimedia extensions and the present media processors. The demand to improve the price-performance ratio for the whole system and to reduce the power consumption makes the media processor evolve into a system processor, which integrates not only the media processor but also the function of a general-purpose microprocessor, various interfaces and DRAMs.

In this paper, we propose a descriptor as a shape signature and the projective refinement as a verification method for recognizing 2D curved objects with occlusions from their partial views. For an extracted curve segment, we compute a series of the geometric invariance of equally spaced five co-planar points on the curve. Thus the resulting descriptor is invariant only under rotation, translation, and scale, but sufficient similarity is preserved even under large distortions. It is more stable and robust since it does not need derivatives. We use this transformation-invariant descriptor to index a hash table. We show the efficiency of the method through experiments using seriously distorted images of 2-D curved objects with occlusions.

We have developed a parallel image processing RAM (PIP-RAM) which integrates a 16-Mb DRAM and 128 processor elements (PEs) by means of 0. 38-µm CMOS 64-Mb DRAM process technology. It achieves 7. 68-GIPS processing performance and 3. 84-GB/s memory bandwidth with only 1-W power dissipation (@ 30-MHz), and the key to this performance is the DRAM design. This paper presents the key circuit techniques employed in the DRAM design: 1) a paged-segmentation accessing scheme that reduces sense amplifier power dissipation, and 2) a clocked low-voltage-swing differential-charge-transfer scheme that reduces data line power dissipation with the help of a multi-phase synchronization DRAM control scheme. These techniques have general importance for the design of LSIs in which DRAMs and logic are tightly integrated on single chips.

We propose a finite-capacity single-vacation model, with close-down/setup times and a Markovian arrival process (MAP), for SVC-based IP-over-ATM networks. This model considers the SVC processing overhead and the bursty nature of IP packet arrivals. Specifically, the setup time corresponds to the SVC setup time and the vacation time corresponds to the SVC release time, while the close-down time corresponds to the SVC timeout. The MAP is a versatile point process by which typical bursty arrival processes like the IPP (interrupted Poisson process) or the MMPP (Markov modulated Poisson process) is treated as a special case. The approach we take here is the supplementary variable technique. Compared with the embedded Markov chain approach, it is more straightforward to obtain the steady-state probabilities at an arbitrary instant and the practical performance measures such as packet loss probability, packet delay time, and SVC setup rate. For the purpose of optimal design of the SVC-based IP-over-ATM networks, we also propose and derive a new performance measure called the SVC utilization ratio. Numerical results show the sensitivity of these performance measures to the SVC timeout period as well as to the burstiness of the input process.

We examine the effectiveness of shaping and policing mechanisms in reducing the inherent variability of fractal traffic, with the objective of increasing network operating points. Whether a shaper simply spaces a flow or allows small bursts according to a leaky bucket, we show using analytical arguments that, i) the Hurst parameter, which describes the asymptotic variability of the traffic, is unaffected; and ii) while the traffic can be made smoother over time scales smaller than one corresponding to the shapers buffer size, fluctuations over longer time scales cannot be appreciably altered. We further show that if shaping is used to reduce buffer size requirements at a network bottleneck, any savings here are offset by the increased buffer requirements at the shapers. Perhaps the most significant deficiency of shaping identified here is that it is necessary to model individual streams to a level of accuracy that is not feasible in practice. In contrast, statistical multiplexing can achieve reasonable network efficiencies by only requiring characterizations of aggregate traffic.

This paper introduces an error controlled decision feedback (ECDF) multiuser receiver, which integrates a successive canceller with linear block channel coding to mitigate decision error propagation. In particular, it uses a switching successive cancellation feedback loop, which can be open if excessive bit errors occur to prevent decision error propagation. The results of computer simulation show that the ECDF receiver possesses advantages in terms of near-far resistance and BER over many reported schemes.

In the future, more and more network providers will be established through the introduction of an open telecommunications market. At this time, it is necessary to guarantee the fair competition between these network providers. In this paper, a negotiation protocol for connection establishment is proposed. This negotiation protocol is based on the concept of open, competitive bidding and can guarantee fair competition between the network providers. In this negotiation protocol, each network providers objective is to maximize its profit. Conversely, each users objective is to select a network provider which will supply as much capacity as required. Employing this negotiation protocol, the users and the network providers can select each other based on their objectives. In this paper, adaptation strategies which network providers and users can adopt under the proposed negotiation protocol framework are also discussed. A network provider which adopts this strategy can obtain enough profit even when the number of connection requests is small relative to the idle bandwidth capacity. Moreover, a user who adopts this strategy can be sure to obtain bandwidth even when the idle bandwidth capacity is small relative to the number of connection requests.

This paper presents a finite buffer M/G/1 queue with two classes of customers who are served by a combination of head-of-the-line priority and buffer reservation schemes. This combination gives each class of customers high or low priorities in terms of both delay and loss. The scheme is analyzed for the model in which one class of customers has high priorities over the other class of customers with respect to both delay and loss. First, steady-state joint probability distribution of the number of each class of customers in the buffer and remaining service time is derived by a supplementary variable method. Second, loss probability and mean waiting time for each class of customers are provided using this probability distribution. Finally, a combination of head-of-the-line priority and buffer reservation schemes is numerically compared with other buffer management schemes in terms of admissible offered load to show its effectiveness under differing QoS requirements.

Weighted Round Robin (WRR) scheduling is an extension of round robin scheduling. Because of its simplicity and bandwidth guarantee, WRR cell scheduling is commonly used in ATM switches. However, since cells in individual queues are sent cyclically, the delay bounds in WRR scheduling grow as the number of queues increases. Thus, static priority scheduling is often used with WRR to improve the delay bounds of real-time queues. In this paper, we show that the burstiness generated in the network is an even greater factor affecting the degradation of delay bounds. In ATM switches with per-class queueing, a number of connections are multiplexed into one class-queue. The multiplexed traffic will have a burstiness even if each connection has no burstiness, and when the multiplexed traffic is separated at the down stream switches, the separated traffic will have a burstiness even if the multiplexed traffic has been shaped in the upstream switches. In this paper, we propose a new WRR scheme, namely, WRR with Save and Borrow (WRR/SB), that helps improving the delay bound performance of WRR by taking into account the burstiness generated in the network. We analyze these cell scheduling methods to discuss their delay characteristics. Through some numerical examples, we show that delay bounds in WRR are mainly dominated by the burstiness of input traffic and, thus WRR/SP, which is a combination of WRR and static priority scheduling, is less effective in improving delay bounds. We show that WRR/SB can provide better delay bounds than WRR and that it can achieve the same target delay bound with a smaller extra bandwidth, while large extra bandwidth must be allocated for WRR.

Bursts from a number of variable bit rate sources allocated to a virtual path with a given capacity can inundate the channel. Buffers used to take care of such bursts can fill up rapidly. The buffer size limits its burst handling capability. With large bursts or a number of consecutive bursts, the buffers fill up and this leads to high cell losses. Channel reconfiguration with dynamic allocation of spare capacities is one of the methods used to alleviate such cell losses. In reconfigurable networks, spare capacity allocation can increase the channel rates for short durations, to cope with the excess loads from the bursts. The dynamic capacity allocations are adaptable to the loads and have fast response times. We propose heuristic rules for spare capacity assignments in ATM networks. By monitoring buffer occupancy, triggers which anticipate excess traffic can be used to assign spare capacities to reduce the cell loss probabilities in the network.

One of the important challenges in the design of ATM networks is how to provide quality-of-service (QoS) while maintaining high network resource utilization. In this paper, we discuss the role of real-time traffic characterization in QoS control for ATM networks and review several approaches to the problem of resource allocation. We then describe a particular framework for QoS control in which real-time measurements of a connection stream are used to determine appropriate parameters for usage parameter control (UPC). Connection admission control (CAC) is based on the characterization of the aggregate stream in terms of the individual stream UPC descriptors, together with real-time measurements.

In this paper an ATM call level model, where service classes with QoS guarantees (CBR/VBR) as well as elastic (best effort) services (ABR/UBR) coexist, is proposed and a number of simulations have been carried out on three different network topologies. Elastic traffic gives on the network level rise to new challenging problems since for a given elastic connection the bottleneck link determines the available bandwidth and thereby put constraints on bandwidth at other links. Thereby bandwidth allocation at call arrivals but also bandwidth reallocation at call departure becomes, together with routing, an important issue for investigation. Two series of simulations have been carried out where three different routing schemes have been evaluated together with two bandwidth allocation algorithms. The results indicate that the choice of routing algorithm is load dependent and in a large range the shortest path algorithm properly adopted to the mixed CBR/ABR environment performs very well.

The classical max-min policy has been suggested by the ATM Forum to support the available bit rate (ABR) service class. However, there are several drawbacks in adopting the max-min rate allocation policy. In particular, the max-min policy is not able to support the minimum cell rate (MCR) requirement and the peak cell rate (PCR) constraint for each ABR connection. Furthermore, the max-min policy does not offer flexible options for network providers wishing to establish a usage-based pricing criterion. In this paper, we present a generic weight-based rate allocation policy, which generalizes the classical max-min policy by supporting the MCR/PCR for each connection. Our rate allocation policy offers a flexible usage-based pricing strategy to network providers. A centralized algorithm is presented to compute network-wide bandwidth allocation to achieve this policy. Furthermore, a simple switch algorithm using ABR flow control protocol is developed with the aim of achieving our rate allocation policy in a distributed networking environment. The effectiveness of our distributed algorithm in a local area environment is substantiated by simulation results based on the benchmark network configurations suggested by the ATM Forum.

This paper presents an efficient bandwidth allocation method for the two-layer video coding of different spatial resolution. We first find a model of distortion-bitrate relationship for the MPEG-2 spatial scalable coding in a fixed total bitrate system. Then we propose an adaptive bitrate allocation method for a constant distortion ratio between two layers with the given total bandwidth. In the proposed method, approximated model parameters are used for simple implementation. The validity of the approximation is proven in terms of the convergence to the desired distortion ratio. It is shown by simulation that the proposed bitrate allocation method can keep almost a constant distortion ratio between two layers in comparison to a fixed bitrate allocation method.