Exploiting the full potential of a multiprocessor system requires a good job scheduling algorithm. In this paper we analyze three dynamic job scheduling algorithms in multiprocessor systems. These algorithms are based on static job scheduling algorithms, LPT (longest processing time first), SJF (shortest job first), and LPR (largest processor requirement first), each of which exhibits good performance in terms of asymptotic upper bound on the makespan of the schedule generated by it. We analyze their performance in the dynamic case experimentally, where we have a stochastic stream of jobs with arbitrary processing time and processor requirement. We compare their performance with the FCFS algorithm and its simple extension. Except for LPT, the algorithms are found to perform significantly better than FCFS, while among themselves SJF performs the best, followed by K-LPR, a variation of LPR. We also consider the fairness aspect of these algorithms and propose a general technique to impose fairness on these algorithms. Finally, we analyze the impact of imposing fairness on the performance of these algorithms.

This paper presents a method, called reduced scan shift, which generates short test sequences for full scan circuits. In this method, scan shift operations can be reduced, i.e., not all but part of flip-flops (FFs) are controlled and observed. This method, unlike partial scan methods, does not decrease fault coverage. In the reduced scan shift, test vectors for the combinational part of a circuit are fistly generated. Since short test sequence will be obtained from the small test vectors set, test compaction techniques are used in the test vector generation. For each test vector in the obtained test set, it is found which FFs should be controlled or observed. And then a scan chain is configured so that FFs more frequently required to be controlled (observed) can be located close to the scan input (output). After the scan chain is configured, the scan shift requirement is examined for the essential faults of each test vector. Essential fault is defined to be a fault which is detected by only one test vector but not other test vectors. The order of test vectors is carefully determined by comparing the scan control requirement of a test vector with the scan observation requirement of another test vector so that unnecessary scan shift operations only for controlling or observing FFs can be reduced. A method of determining the order of test vectors with state transition is additionally described. The effectiveness of the proposed method is shown by the experimental results for benchmark circuits.

A 3.2 GHz, 50 mW, 1 V, GaAs clock pulse generator (CG) based on a phase-locked loop (PLL) circuit has been designed for use as an on-chip clock generator in future high speed processor LSIs. 0.5 µm GaAs MESFET and DCFL circuit technologies have been used for the CG, which consists of 224 MESFETs. An "enhanced charge-up current" inverter has been specially designed for a low power and high speed voltage controlled oscillator (VCO). In this new inverter, a voltage controlled dMESFET is combined in parallel with the load dMESFET of a conventional DCFL inverter. This voltage controlled dMESFET produces an additional charge-up current resulting in the new VCO obtaining a much higher oscillation frequency than that of a ring oscillator produced with a conventional inverter. With a single 1 V power supply (Vdd), SPICE calculation results showed that the VCO tuning range was 2.25 GHz to 3.65 GHz and that the average VCO gain was approximately 1.4 GHz/V in the range of a control voltage (Vc) from 0 to 1 V. Simulation also indicated that at a Vdd of 1 V the CG locked on a 50 MHz external clock and generated a 3.2 GHz internal clock (=50 MHz64). The jitter and power dissipation of the CG at 3.2 GHz oscillation and a Vdd of 1 V were less than 8.75 psec and 50 mW, respectively. The typical lock range was 2.90 GHz to 3.59 GHz which corresponded to a pull-in range of 45.3 MHz to 56.2 MHz.

Video compression technologies such as MPEG have enabled the efficient use of video data in the computer environment. However, the compressed video information still has a huge amount of data compared with the other media such as text, audio, and graphics. Therefore, it is very important to handle the video information in a networked database for the efficient use of resources like storage media. Furthermore, in the networked database, its retrieval methods including search and delivery become the key issues especially for the video information which requires a large network bandwidth. In this paper, a video browsing method using an automatic fast scene cut detection for networked video database access is described. The scene cut is defined as the scene change frame and is detected by temporal change in interframe luminance difference and chrominance correlation which are obtained from spatio-temporally scaled image directly extracted from the MPEG compressed video without any complex processing of video decoding. The detected scene change frames are further investigated to exploit the relationship between the scene cuts and are classified in order to make a hierarchical indexing. These results of detection are stored as an scene index file using the MPEG format. The simulation results are also presented for several test video sequences to show that these methods have enabled the efficient video database construction and accessing.

In this paper, chaos synchronization in coupled discrete-time dynamical systems is studied. Computer results display the interesting synchronization behaviors in the mutually coupled systems. As possible applications of chaos synchronization, parameter estimations and secure communications are proposed. Furthermore, a modified OGY method is given, which converts a chaotic motion into a periodic motion.

Considering the trend towards adopting high efficiency picture coding schemes into digital broadcasting services, we investigate objective picture quality scales for evaluating digitally encoded still and moving pictures. First, the study on the objective picture quality scale for high definition still pictures coded by the JPEG scheme is summarized. This scale is derived from consideration of the following distortion factors; 1) weighted noise by the spatial frequency characteristics and masking effects of human vision, 2) block distortion, and 3) mosquito noise. Next, an objective picture quality scale for motion pictures of standard television coded by the hybrid DCT scheme is studied. In addition to the above distortion factors, the temporal frequency characteristics of vision are also considered. Furthermore, considering that all of these distortions vary over time in motion pictures, methods for determining a single objective picture quality value for this time varying distortion are examined. As a result, generally applicable objective picture quality scale is obtained that correlates extremely well with subjective picture quality scale for both still and motion pictures, irrespective of the contents of the pictures. Having an objective scale facilitates automated picture quality evaluation and control.

A new approach is described for the datapath scheduling of behavioral descriptions containing nested conditional branches of arbitrary structures. This paper first investigates such a complex scheduling mechanism, and formulates an optimal scheduling problem as a 0-1 integer programming problem such that given a prescribed number of control steps, the total cost of functional units can be minimized. In this formulation, each constraint is expressed in the form of a Boolean function, which is set equal to 1 or 0 according as the constraint is satisfied or not, respectively, and a satisfiability problem is defined by the product of the Boolean functions. A procedure is then described, which intends to seek an optimal solution by means of a branch-and-bound method on a binary decision diagram representing the satisfiability problem. Experimental results are also shown, which demonstrate that our approach is of more practical use than the existing methods.

Electromagnetic plane wave scattering by a loaded trough on a ground plane has been analyzed by Kobayashi and Nomura's method. The field in each region is expressed first in terms of appropriate eigen functions, whose excitation coefficients are determined by the continuity condition across the aperture of the trough. Simple far field expression which is suitable for numerical calculation for small aperture cases has been derived. Scattering far field patterns and radar cross section are calculated and compared with those obtained by other methods. Good agreements have been observed for all incident angles.

In their paper[1], Sasase and Mori proposed a method of calculating the resequencing delay for a multiple-server queueing system under a threshold-type scheduling. However, it is found that the result of the proposed method does not converge to the corresponding expression in Ref.[2] for the system with two servers. In this correspondence, we show that the proposed method in Ref.[1] is not correct, and verify it by simulation.

This paper presents the results of a study made to determine the line length coverage of the high-bit-rate digital subscriber line (HDSL) present in NTT's local networks. The HDSL carries one bi-directional 784 kbit/s channel per pair and supports the digital interface at 1544kbit/s by using two cable pairs. The primary purpose of this study is to estimate the range limits for candidate transmission schemes considering line installation conditions, and to determine the most promising transmission scheme and its feasibility given the environment of NTT's local networks. Pulse amplitude modulation (PAM) and quadrature amplitude modulation (QAM) transmission schemes are compared for HDSL implementation. It is shown that 2B1Q-PAM and 16-QAM generally achieve better performance than the more complicated PAM and QAM given the presence intra-system crosstalk interference (interference between identical transmission systems). The range limits determined by inter-system crosstalk interference (interference between different transmission systems) with basic rate access (BRA) implementing a burst-mode transmission method are also estimated. This paper concludes that 2B1Q-PAM achieves the best overall performance in NTT's local networks. A feasibility study of 192-6144 kbit/s transmission is also described.

In a hybrid coder which employs motion compensation and discrete cosine transform (MC-DCT coder), up to 90% of bits are used to represent the quantized DCT blocks. So it is most important to represent them with as few bits as possible. In this paper, we propose an efficient method for encoding the quantized DCT blocks of motion compensated prediction (MCP) errors, which adaptively selects one of a few scanning patterns. The scanning pattern selection of an MCP error block is based on the motion compensated images which are always available at the decoder as well as at the encoder. No overhead information for the scanning patterns needs to be transmitted. Simulation results show that the average bit rate reduction amounts to 5%.

In current teleteaching systems, video conferencing systems have been used to transmit a motion video from a teacher's site. A video that captures a teacher or his or her chalkboard is transmitted to a remote site through a communication channel. Since the resolution of the video is not very high, a camera captures either a teacher or a chalkboard, but not both at the same time. Thus, remote students have difficulty in obtaining realistic sensation. Another approach to realizing teleteaching is to use a computer-based desktop conferencing system that supports a motion video and a computer-based shared chalkboard. In this approach, a teacher has to use a mouse or a handwriting tablet for input, and therefore cannot use a real chalkboard. Moreover, the teacher cannot use gestures to remote students. This paper presents a multimedia teleteaching system that integrates an electronic whiteboard with a multimedia desktop conferencing system for providing realistic sensation to remote students. The system provides two-way communication of a video and a computerized chalkboard. A teacher uses an electronic whiteboard as a real whiteboard using direct manipulation, and transmits his or her gestures to remote students by using video communication. The system provides dual views; one view is for teacher's gestures and the other is for chalkboard contents. By providing the dual views, the system can transmit teacher's gestures all the time. Since chalkboard contents are processed and displayed as computer data, students can see them clearly. With the computerized chalkboard, a teacher or a student can zoom contents, input data written on a paper using a scanner, or add annotation.

The double-stage threshold-type foreground-background congestion control for the common-store queueing system with multiple nonpreemptive priority classes is proposed to improve the transient performance, where the numbers of accepted priority packets in both foreground and background stores are controlled under the double-stage threshold-type scheduling. In the double-stage threshold-type congestion control, the background store is used for any priority packets, and some parts of the background store are reserved for lower-priority packets to accommodate more lower-priority packets in the background store, whereas some parts of the foreground store are reserved for higher-priority packets to avoid the priority deadlock. First, we derive the general set of coupled differential equations describing the system-state, and the expressions for mean system occupancy, throughput and loss probability. Second, the transient behavior of system performance is evaluated from the time-dependent state probabilities by using the Runge-Kutta procedure. It is shown that when the particular traffic class becomes overloaded, high throughputs and low loss probabilities of other priority classes can be obtained.

A simple solution for the right-angle H-plane waveguide double bend is obtained in analytic series form. The simultaneous equations are solved to obtain the transmission and reflection coefficients in fast convergent series forms. The numerical computations are performed to show the behaviors of the transmission coefficient versus frequency.

This paper proposes the concept of Tool-Based Direct Deformation Method (TB-DDM) which supports networked CAD (Computer Aided Design) systems with virtual reality technologies. TB-DDM allows designers to sculpt free forms directly with tools; each tool has its deforming characteristics, such as, the area and the shape of deformation. TB-DDM's direct deformation interface is independent of form representations because the system automatically calculates appropriate deformation according to its form representation when a tool pushes" a form. The deformation with TB-DDM is concisely described by the initial shape, types of tools, and thier loci; the description enables cooperative CAD systems with narrow bandwidth network to share design process rapidly and to distribute computational load.

A new rate-controlled queueing discipline, called virtual rate-based queueing (VRBQ), is proposed for packet-switching nodes in connection-oriented, high-speed, wide-area networks. The VRBQ discipline is based on the virtual rate which has a value between the average and peak transmission rates. By choosing appropriate virtual rates, various requirements can be met regarding the performance and quality of services in integrated-service networks. As the worst-case performance guarantee, we determine the upper bounds of queueing delay when VRBQ is combined with an admission control mechanism, i.e., Dynamic Time Windows or Leaky Bucket. Simulation results demonstrate the fairness policy of VRBQ in comparison with other queueing disciplines, and the performance of sources controlled under different virtual rates.

In this letter we present an electronic circuit based on a neural net to compute the discrete Walsh transform. We show both analytically and by simulation that the circuit is guaranteed to settle into the correct values.

This paper discusses and evaluate a high speed multimedia communications in ATM networks. Communication platforms below AAL layer in ATM networks can provide fairly high speed communication channel for ATM-UNI. On the other hand, the conventional data processing architecture in the workstations can not provide sufficient throughput compared to the throughput of ATM networks at this time. Also, regarding error-free peer-to-peer data communications, conventional transport protocol, e.g. TCP, can not provide small latent communication, when the product of communication bandwidth and propagation delay is large. This paper focuses on protocol architecture, especially on error control policy at SSCS in AAL layer, and on performance evaluation of high speed multimedia communication based on the current data processing architecture.

In this paper, we present a digital scheme for fast VLSI range imaging sensor, which is a modification of the analog scheme of existing sensor implemented by T. Kanade. Instead of reading timing information in analog manner, we use a digital scheme which has several advantages over the analog scheme, including area saving, insusceptibility to noise and other undesirable effects. We have implemented a prototype to test feasibility and present its experimental result.

A method is presented for reconstructing the surface profile of a perfectly conducting rough surface boundary from the measurements of the scattered far-field. The proposed inversion algorithm is based on the use of the Kirchhoff approximation and in order to determine the surface profile, the Fletcher-Powell optimization procedure is applied. A number of numerical results illustrating the method are presented.