In the last three decades, task scheduling problems onto parallel processing systems have been extensively studied. Some of those problems take communication delays into account. In most of previous works, the structure of the parallel processing systems of the scheduling problem is restricted to be fully connected. However, the realistic models of parallel processing systems, such as hypercubes, grids, tori, and so forth, are not fully connected and the communication delay has a great effect on the completion time of tasks. In this paper, we show that the problem of scheduling tasks onto a hypercube/grid is NP-complete even if the task set forms an out- or in-tree and the execution time of each task and each communication take one unit time. Moreover, we construct linear time algorithms for computing an optimal schedule of some classes of binary and ternary trees onto a hypercube if each communication has one unit time.
Sangkil JUNG Gooyoun HWANG Changhwan OH
This paper proposes three-phased traffic conditioner (3PTC) to be installed at edge routers in Differentiated Services (DiffServ) networks. 3PTC ensures that Assured Service (AS) flows are supplied with the throughput assurance, which stems from alleviating the impact of the size of TCP reserved rate, UDP/TCP interaction, Round Trip Time (RTT) and number of microflows. 3PTC is composed of token bucket phase, writing probability (WP) calculation phase and queue management phase. Computer simulation results show that 3PTC guarantees throughput assurance and provides end users with expected service levels.
This letter investigates sidelobe levels of a two-bit digital phased array composed of a small number of elements. Among several phase shifter designs applicable to phased arrays, a two-bit design needs the least number of circuit elements so that the development and manufacturing need the lowest cost. Now the following questions arise. Is a two-bit phased array practical? How low can its sidelobe level be reduced? To answer the questions, three methods are tried to reduce the sidelobe level of a uniformly-excited linear array of isotropic elements. The methods are the quadratic-phase feed method, the partially randomizing method of periodic phase errors, and the genetic algorithm (GA) approach. Among the methods, the quadratic-phase feed method provides the lowest sidelobe level around -12.5 dB - -13.2 dB in the steering angles from 0 to 48 degrees for a 21-element, half-wavelength spacing array, and -11.2 dB - -13.0 dB in the steering angles from 0 to 30 degrees for an 11-element, 0.6-wavelength spacing array. Although it depends on the system requirement, these values would be acceptable in some applications, hence a two-bit phased array designed properly may be practical in an actual system.
Ultra shallow low-resistive junction formation has been investigated for sub-100-nm MOSFETs using antimony implantation. The pileup at the Si/SiO2 interface and the resulting dopant loss during annealing is a common obstacle for antimony and arsenic to reduce junction sheet resistance. Though implanted arsenic gives rise to pileup even with a few seconds duration RTA (Rapid Thermal Annealing), antimony pileup was suppressed with the RTA at relatively low temperature, such as 800 or 900. As a result, low sheet resistance of 260 Ω/sq. was obtained for a 24 nm depth junction with antimony. These results indicate that antimony is superior to arsenic as a dopant for ultra shallow extension formation. However, increase in antimony concentration above 11020 cm-3 gives rise to precipitation and it limits the sheet resistance reduction of the antimony doped junctions. Redistribution behaviors of antimony relating to the pileup and the precipitation are discussed utilizing SIMS (Secondary Ion Mass Spectrometry) depth profiles.
Michinobu NAKAO Yoshikazu KIYOSHIGE Koichiro NATSUME Kazumi HATAYAMA Satoshi FUKUMOTO Kazuhiko IWASAKI
This paper presents a new deterministic built-in test scheme using a neighborhood pattern generator (NPG) to guarantee complete fault efficiency with small test-data storage. The NPG as a decoding logic generates both a parent pattern and deterministic child patterns within a small Hamming distance from the parent pattern. A set of test cubes is encoded as a set of seeds for the NPG. The proposed method is practically acceptable because no impact on a circuit under test is required and the design of the NPG does not require the results of test generation. We also describe an efficient seed generation method for the NPG. Experimental results for benchmark circuits demonstrate that the proposed method can significantly reduce the storage requirements when compared with other deterministic built-in test methods.
Satoko MAMADA Kazuhisa MAKINO Satoru FUJISHIGE
In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n2) time algorithm for the sink location problem, where n is the number of vertices in the network.
Multicast is an efficient way to send messages to a group of members. It is becoming the basis for a number of applications, such as teleconferencing, news groups, and on-line games. Security is one of the main issues in realizing multicast communications. A working group within IETF dedicated to multicast security has been formed and RFCs and working drafts concerning multicast security are proposed. This letter analyzes the security of a scheme proposed in [1] for securely establishing a shared, secret key in a large, dynamic group. We show that it fails to provide forward and backward security.
Xiaobei LIU Soo Ngee KOH Susumu YOSHIDA
Soft bit speech decoding, as a new approach of error concealment, is applied to the mixed excitation linear prediction (MELP) algorithm. Average residual redundancies of the quantized parameters are exploited in the error concealment process as an a priori knowledge of the source. Results show a significant SNR improvement for parameters decoded using the error concealment scheme.
Yoshiyuki KUSAKARI Masaki SATO Takao NISHIZEKI
A linkage is a collection of line segments, called bars, possibly joined at their ends, called joints. A planar reconfiguration of a linkage is a continuous motion of their bars, preserving the length of each bar and disallowing bars to cross. In this paper, we introduce a class of linkages, called "monotone trees," and give a method for reconfiguring a monotone tree to a straight line. If the tree has n joints, then the method takes at most n-1 moves, each of which uses two joints. We also obtain an algorithm to find such a method in time O(n log n), using space O(n). These time and space complexities are optimal.
Chien-Hsing WU Chien-Ming WU Ming-Der SHIEH Yin-Tsung HWANG
In this paper, we present the division algorithm (DA) for the computation of b=c/a over GF(2m) in two aspects. First, we derive a new formulation for the discrete-time Wiener-Hopf equation (DTWHE) Ab = c in GF(2) over any basis. Symmetry of the matrix A is observed on some special bases and a three-step procedure is developed to solve the symmetric DTWHE. Secondly, we extend a variant of Stein's binary algorithm and propose a novel iterative division algorithm EB*. Owing to its structural simplicity, this algorithm can be mapped onto a systolic array with high speed and low area complexity.
The main objective of vehicle suspensions is to improve ride comfort and road holding ability. Though passive suspensions consist of spring and damper, active suspensions adopt an actuator in addition to passive suspensions. In this paper, a quarter car model with an asymmetric hydraulic actuator is used. Moreover, the damping coefficient of the damper, which is changed according to the actuator velocity, is considered. The LPV (Linear Parameter Varying) model is obtained by applying feedback linearization technique. Next, a gain-scheduled controller, based on LQ regulator with different weighting factor, is designed according to the actuator velocity and the stability of the proposed controller is also proved. The effectiveness of the proposed controller is shown by numerical simulations.
In this paper, a novel method to reduce additive time-varying noise is proposed. Unlike the previous methods, the proposed method requires neither the assumption about noise nor the estimate of the noise statistics from any pause regions. The enhancement is performed on a band-by-band basis for each time frame. Based on both the decision on whether a particular band in a frame is speech or noise dominant and the masking property of the human auditory system, an appropriate amount of noise is reduced in time-frequency domain using modified spectral subtraction. The proposed method was tested on various noisy conditions: car noise, F16 noise, white Gaussian noise, pink noise, tank noise and babble noise. On the basis of segmental SNR, inspection of spectrograms and MOS tests, the proposed method was found to be more effective than spectral subtraction with and without pause detection in reducing noise while minimizing distortion to speech.
A communication model and a computer assisted communication method are introduced. With this model incorrect communications between humans are explained and then a method to lead successful communications with computer is illustrated. This method improves qualities of communications and can be applied to co-operative works. On the basis of the communication method, we have been developing a co-operative visual software requirements definition method via network with a visual requirements language named VRDL. Our method will improve quality of software requirements specification (SRS).
Deogkyoo LEE Daekeun MOON Ilgu YUN Hagbae KIM
Since components faults occurring at arbitrary places (primarily on the links) affect seriously network performance and reliability, the multicomputers operating in harsh environments should be designed to guarantee normal network-missions in presence of those faults. One solution to the end is a fault-tolerant routing scheme, which enables messages to safely reach their destinations avoiding failed links when transmission of messages is blocked by certain faults. In the paper, we develop a fault-tolerant routing algorithm with deadlock freedom in an n-dimensional meshed network, and validate its efficiency and effectiveness through proper simulations. The aspects of fault-tolerance is adopted by appending partial-adaptiveness and detouring to the e-cube algorithm, while using a wormhole routing for the backbone routing method. The phenomenon of deadlock incurred due to its adaptiveness is eliminated by classifying a physical channel into a couple of virtual channels.
Atsuo HAZEYAMA Naota SAWABE Seiichi KOMIYA
The group organization used for group learning in a knowledge intensive domain like software development affects educational achievement. This paper proposes a group organization system for software engineering education done through group learning. The organizational problem itself is defined and why a Genetic Algorithm (GA) is an appropriate means of solving this problem is explained. This system is a Web application developed with open source software and runs on an open source software platform. Based on the group organization data collected from actual classes, we generated various group organizations by using different strategy parameter values. We then gave a questionnaire to actual students asking them which solution produced the fairest group organization. The replies received revealed that the candidate solution that set greater weight on leadership capability and system analysis capability was the fairest.
Suguru AMITANI Toshinori YAMADA Shuichi UENO
It is a fundamental problem to construct a virtual path layout minimizing the hop number as a function of the congestion for a communication network. It is known that we can construct a virtual path layout with asymptotically optimal hop number for a mesh of trees network, butterfly network, cube-connected-cycles network, de Bruijn network, shuffle-exchange network, and complete binary tree network. The paper shows a virtual path layout with minimum hop number for a complete binary tree network. A generalization to complete k-ary tree networks is also mentioned.
Kiyoshi NISHIKAWA Hitoshi KIYA
In this paper, we propose the multirate repeating method for alias free subband adaptive filters (AFSAFs) and consider its convergence property. It is shown that we can adjust the convergence speed and the final error of the adaptive filters by varying its two parameters according to the requirements of the applications where the method is applied. The proposed method has two parameters, namely, the number of channel and the number of repetition. We show that by increasing the number of channels we can reduce the final error, and this property is preferred when the signal-to-noise ratio (SNR) is low. On the other hand, we show that the convergence speed of the AFSAF approaches to that of the affine projection algorithm (APA) by increasing the number of repetition. Through the computer simulations, we show the effect of the proposed method.
Jar-Ferr YANG Rong-San LIN Seric HU
The long-term predictor (LTP) can effectively reduce the redundancy of the quasi-periodicity of speech signals. Traditional pitch predictors in linear predictive coding systems are developed by assuming that pitch gains are constant in each processing subframe. In this paper, we introduce a time-varied prediction gain to achieve a better representation of speech periodicity than the traditional approach. Due to the non-stationary variation of speech, the proposed LTP method can trace the detailed fluctuation of speech amplitude in both transient and stationary periods. Simulation results show that the proposed first-order varied-gain pitch predictor obtains a near speech quality as the fifth-order pitch predictor of the G.723.1 coder does; however, the former requires much lower computation than the latter.
Futoshi FURUTA Kazuo SAITOH Kazumasa TAKAGI
We have designed a demultiplexer (DMUX) with a simple structure, high-speed operation circuits and large bias margins. By using a binary-tree architecture and clock-driven circuits, multi-channel DMUXs can be constructed easily from the same elemental circuits, i.e., 1-to-2 DMUX, consisting of a T-FF and a 1-to-2 switch. By applying cell-level optimization and Monte Carlo simulation, bias margins and operation frequency of the circuits were enlarged. Logical operations of the 1-to-2 DMUX and a multi-channel DMUX, e.g., a 1-to-4 DMUX were experimentally confirmed. It was also confirmed that the large margins, 33% of the DMUX (1-to-2 switch) was kept up regardless the degree of integration, and that the 1-to-2 DMUX can operate up to 46 GHz by using measure of average voltages across Josephson junctions.
Roberto Y. OMAKI Gen FUJITA Takao ONOYE Isao SHIRAKAWA
A wavelet based algorithm for scalable video compression is described, with the main focus put on memory bandwidth reduction and efficient VLSI implementation. The proposed algorithm adopts a modified 2-D subband decomposition scheme in conjunction with a partial zerotree search for efficient Embedded Zerotree Wavelet coding. The experiment with the performance of the proposed algorithm in comparison with that of conventional DWT, MPEG-2, and JPEG demonstrates that the image quality of the proposed algorithm is consistently superior to that of JPEG, and our scheme can even outperform MPEG-2 in some cases, although it does not exploit the inter-frame redundancy. In spite of the performance inferiority to the conventional DWT, the proposed algorithm attains significant reduction of DWT memory requirements, enhancing a reasonable balance between implementation cost and image quality.