All the existing scheduling algorithms order the instructions of the program in such a way that it can be executed in minimal time only for one fixed number of processors. In this paper we propose a new scheduling method, called Parallelism-Independent Scheduling Method, which enables the execution of the scheduled program on parallel computers with any degree of parallelism in near-optimal time. We propose three Parallelism-Independent algorithms, which have the following phases: obtaining a parallel schedule by using a list scheduling heuristics, optimization of the parallel schedule by rearranging the tasks in each level, so that they can be executed efficiently with different degrees of parallelism, serialization of the parallel schedule, and insertion of markers for the parallel execution limits. The three algorithms differ in their optimization phase. To prove the efficiency of our algorithms, we have made simulations with random directed acyclic graphs with different size and degree of parallelism. We compared the results in terms of schedule length to those obtained using the Critical Path Algorithm separately for each degree of parallelism.

This paper describes a highly performance scalable video coder. Wavelet transform is employed to decompose the video frame into different resolutions. Novel features of this coder are 1) a highly efficient multi-resolution motion estimation that requires minimum compuation and overhead motion information is embedded in this scheme; 2) the wavelet coefficients are organized in an extended zero tree (EZT) which is much more efficient than the simple zerotree. We show with experimental results that this video coder achieves good performances both in processing time and compression ratio when applied to typical test video sequences.

The Monte Carlo simulation is applied to fault tree analyses of the sequential failure logic. In order to make the validity of the technique clear, case studies for estimation of the statistically expected numbers of system failures during (0, t] are conducted for two types of systems using the multiple integration method as well as the Monte Carlo simulation. Results from these two methods are compared. This validates the Monte Carlo simulation in solving the sequential failure logic with respectably small deviation rates for those cases.

This paper describes a crossbar-switch arbiter for a high-speed MAPOS switch. The arbiter uses the following techniques suitable for variable-length frame switching: 1. parallel processing for handling requests from network interfaces and for resource allocation, 2. techniques such as release-on-request, fast back-to-back transfer, and request prefetching to reduce the arbitration overhead, and 3. a resource sampling technique to enable efficient one-shot multicast processing. Our simulation-based performance evaluation and estimation of the scale of its logic circuits indicated that this arbiter can be implemented through simple hardware.

Adaptive Agent Oriented Software Architecture (AAOSA) is a new approach to software design based on an agent-oriented architecture. In this approach, agents are considered adaptively communicating concurrent modules that are divided into a "white box" module responsible for communications and learning and a "black box" which is responsible for the independent specialized processes. An AAOSA system is actually parsing input in the interpretation phase. We will show that AAOSA can be applied to the parallel, and distributed parsing of context sensitive languages.

This paper describes an improved complementary beamforming microphone array based on the new noise adaptation algorithm. Complementary beamforming is based on two types of beamformers designed to obtain complementary directivity patterns with respect to each other. In this system, during a pause in the target speech, two directivity patterns of the beamformers are adapted to the noise directions of arrival so that the expectation values of each noise power spectrum are minimized in the array output. Using this technique, we can realize the directional nulls for each noise even when the number of sound sources exceeds that of microphones. To evaluate the effectiveness, speech enhancement experiments and speech recognition experiments are performed based on computer simulations with a two-element array and three sound sources under various noise conditions. In comparison with the conventional adaptive beamformer and the conventional spectral subtraction method cascaded with the adaptive beamformer, it is shown that (1) the proposed array improves the signal-to-noise ratio (SNR) of degraded speech by more than 6 dB when the interfering noise is two speakers with the input SNR of below 0 dB, (2) the proposed array improves the SNR by about 2 dB when the interfering noise is bubble noise, and (3) an improvement in the recognition rate of more than 18% is obtained when the interfering noise is two speakers or two overlapped signals of some speakers under the condition that the input SNR is 10 dB.

A novel K-band MMIC frequency doubler has been developed using resistive series feedback circuit. The doubler exhibits much better D/U ratio, smaller output power variation against ambient temperature and lower power consumption than those of the conventional single-ended doubler. This paper presents the simulation results on the effect of the resistive series feedback by harmonic balance methods. To obtain practical and accurate simulation results, newly developed gate charge model for Cgs and Cgd is introduced. The fabricated result of the proposed MMIC is also demonstrated.

We study the evolution and the dominance of the service based functions and their distinguishing features. As the service industry matures, its functions bear many similarities with the software development processes, such as intense man-machine interaction, knowledge intensive activities, flexibility in the organization, control and execution of tasks. In this paper we discuss wide range of interconnected topics, emphasizing the multi-faceted nature of service functions. These include the evolution of service industry and their products, the consumerization of high tech products based on their large-scale adoption and the consequent creation of implicit requirements; the technology transfer processes; the error proneness due to intense and prolonged interaction with computers and some methods of mitigating error incidence. We argue that by proper 'humanization and personalization' of interactive systems and by the use of teams of computer supported professionals, we can prevent such errors. We discuss some useful team types, models of their behavior and their control aspects. As the cost of communications shrinks like due to the Internet, we conclude that a fully decentralized system control provides a flat, flexible, and fair and friction-free organization for large team based service systems.

A per-connection end-to-end call admission control (CAC) problem is solved in this paper to allocate network resources to an input session to guarantee its quality of service (Qos) requirements. In conjunction with the solution of the CAC problem, a traffic descriptor is proposed to describe the loss rate and the delay bound Qos requirements of the connection to be set up as well as the statistical characteristics of the associated input traffic which is modeled as a linear mean function plus a (zero-mean) fractional Brownian motion. The information in the traffic descriptor is sufficient to determine the allocation of channel bandwidth and buffer space to the input traffic in a network which employs leaky bucket shapers and scheduling algorithms to guarantee the Qos requirements. The CAC problem is solved by an iterative algorithm of which there are two stages in each iteration: one is responsible for the search of a candidate end-to-end routing path and the other for the verification of the legitimacy of this candidate path to meet the Qos requirements and for the allocation of resources in such a legitimate path.

We propose a wideband CELP-type speech coder at 16 kb/s based on a mel-generalized cepstral (MGC) analysis technique. MGC analysis makes it possible to obtain a more accurate representation of spectral zeros compared to linear predictive (LP) analysis and take a perceptual frequency scale into account. A major advantage of the proposed coder is that the benefits of MGC representation of speech spectra can be incorporated into the CELP coding process. Subjective tests show that the proposed coder at 16 kb/s achieves a significant improvement in performance over a 16 kb/s conventional CELP coder under the same coding framework and bit allocation. Moreover, the proposed coder is found to outperform the ITU-T G. 722 standard at 64 kb/s.

A reallocation problem is defined as determining whether blocks can be moved from their current boxes to their destination boxes in the number of moves less than or equal to a given positive integer. This problem is defined simply and has many practical applications. We previously proved the following results: The reallocation problem such that the block volume is restricted to one volume unit for all blocks can be solved in linear time. But the reallocation problem such that the block volume is not restricted is NP-complete, even if no blocks have bypass boxes. But the computational complexity of the reallocation problems such that the range of the block volume is restricted has not yet been known. We prove that the reallocation problem is NP-complete even if the block volume is restricted to one or two volume units for all blocks and no blocks have bypass boxes. Furthermore, we prove that the reallocation problem is NP-complete, even if there are only two blocks such that each block has the volume units of fixed positive integer greater or equal than two, the volume of the other blocks is restricted to one volume unit, and no blocks have bypass boxes. Next, we consider such a block that must stays in a same box both in the initial state and in the final state but can be moved to another box for making room for other blocks. We prove that the reallocation problem such that an instance has such blocks is also NP-complete even if the block volume is restricted to one volume unit for all blocks.

Pure green ZnTe light-emitting diodes (LEDs) were first realized reproducibly based on high quality ZnTe substrates and a simple thermal diffusion process. This success which overcomes the compensation effect in II-VI materials is due to the use of high quality p-type ZnTe single crystals with low dislocation densities of the level of 2000 cm-2 grown by the vertical gradient freezing (VGF) method and the suppression of as compensating point defects by low temperature annealing with covering the surface of the substrates by the deposition of n-type dopant, Al. The thermal diffusion coefficient and the activation energy of Al were determined from the pn interface observed by scanning electron spectroscopy (SEM). The formation of the intrinsic pn junctions was confirmed from the electron-beam induced current (EBIC) observation and I-V measurement. The bright 550 nm electroluminescence (EL) from these pn-junctions was reproducibly observed under room light at room temperature, with the lifetime exceeding 1000 hrs.

To bridge a wide gap between the end users and the requirements engineers, we propose a business flow diagram for acquiring users' requirements of the object oriented software development in the business application domain. Each field of this diagram shows either a role or a responsibility of a particular person or an organization. This paper proposes a development method that the engineers acquire the requirements by using our diagrams. We have implemented a supporting tool based on this study for collaborating the requirements engineers with their users. At first, the end users of an information system to be developed draw diagrams representing the flows of information and physical objects in their work from their own points of view. Sometimes the engineers write them with the users. If all users submit their diagrams, then our tool collects them and constructs a total diagram. The requirements engineers analyze the total diagram for improving the business flow. After the engineers complete this diagram, our tool can automatically transform it into an initial version of the class diagram. We show the effectiveness of our approach with some experiments. Comparing the related works, we discuss some issues of the practical aspects of this proposal.

This paper discusses the characteristics of human design knowledge. By studying a number of actual human made designs of excellent designers, the most frequent basic mental operations of a typical human designer have been found. They are: a design rule for hierarchical detailing reported previously, a micro design rule for generating a hierarchical expansion, dictionary operations to build a micro design rule and dictionaries. This study assumes a multiplicity of knowledge based on Zipf's theory, "the principle of least effort. " Zipf's principle may be proved and it becomes possible to understand the fundamental nature of human design.

In a software maintenance phase, since quality assurance engineers frequently only change source codes, the consistency between the source codes and their specification documents cannot be kept. In this paper we propose a supporting technique for changing specification documents automatically so that the specifications can be consistent with the source codes. In our technique, we represent a program with multiple graphs and we consider the changes on programs as the modification of the graphs. The modification of the graphs is formalized with a sequence of the operation on the graphs. We design the rules of how to relate the operations on program graphs to the operations on graphs that represent specification documents. By applying these rules, we can detect what modification and which parts of the specification document should be made to maintain the consistency between the specification and the program, when the program is modified.

Distributed shared memory (DSM) systems on top of network of workstations are especially vulnerable to the impact of false sharing because of their higher memory transaction overheads and thus higher false sharing penalties. In this paper we develop a dynamic-granularity shared memory management scheme that eliminates false sharing without sacrificing the transparency to conventional shared-memory applications. Our approach utilizes a special threaded splay tree (TST) for shared memory information management, and a dynamic token-based path-compression synchronization algorithm for data transferring. The combination of the TST and path compression is quite efficient; asymptotically, in an n-processor system with m shared memory segments, synchronizing at most s segments takes O(s log m log n) amortized computation steps and generates O(s log n) communication messages, respectively. Based on the proposed scheme we constructed an experimental DSM prototype which consists of several Ethernet-connected Pentium-based computers running Linux. Preliminary benchmark results on our prototype indicate that our scheme is quite efficient, significantly outperforming traditional schemes and scaling up well.

Laser diodes in the (Al, Ga, In) N system are attractive for many applications. Due to the wurtzite crystal structure, cleaved facets are not easily produced. We have investigated distributed feedback (DFB) laser diodes employing embedded dielectric gratings with the grating located above the active region. The dielectric gratings are incorporated via epitaxial lateral overgrowth. The DFB laser diodes had reduced threshold current densities over the etched cavity devices, with a minimum of 15 kA/cm2. The spectral emission width was considerably reduced for the DFB devices. Voltages for the DFB devices were high due to the presence of the Si3N4 grating within the p-type material.

This paper proposes a fast method of calculating high-order backward Linear Prediction (LP) coefficients for wideband Code Excited LP (CELP) coders operating at around 16 kbit/s. The fast calculation is achieved by a recursive calculation for the high-order autocorrelation of the decoded signal. The recursive calculation can be employed thanks to a novel method of converting the autocorrelation of the decoded signal to that of the residual signal. High-order backward LP coefficients are computed from the autocorrelation of the residual signal using the Levinson-Durbin (LD) procedure. The conversion approximately performs inverse-filtering using LP coefficients representing a corresponding envelope spectrum. Due to the recursive calculation, the proposed fast calculation method achieves 30% to 45% reduction in computations to calculate the high-order backward LP coefficients compared to the conventional method. Subjective tests show that a wideband Multi-Pulse based CELP (MP-CELP) coder at 16 kbit/s with the proposed method achieves comparable coding quality to that with the conventional one with 35% reduction in computations needed for calculation of the backward LP coefficients.

Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.

Excitonic optical properties of GaN homoepitaxial layers have been studied by means of magneto-luminescence and time-resolved luminescence spectroscopy. The luminescence lines due to the radiative recombination of excitons bound to neutral donors and acceptors have been measured under magnetic field up to 8 T, which was aligned perpendicular and parallel to the hexagonal c-axis. Under the magnetic field aligned perpendicular to the hexagonal c-axis, both the donor- and acceptor-bound-exciton lines clearly split into two components, which originated from the Zeeman splitting. The effective g-factors for both the donor- and acceptor-bound excitons were estimated to be 2.02 and 2.47, respectively. Under the magnetic field aligned parallel to the hexagonal c-axis, slight broadening of the bound-exciton lines was observed and the Zeeman splitting was too small to be detected. On the other hand, the diamagnetic shift for both the donor- and acceptor-bound-exciton luminescence lines was observed under the magnetic field aligned both perpendicular and parallel to the hexagonal c-axis. It was found that the diamagnetic shift of the donor-bound exciton was smaller than that of the acceptor-bound exciton. Furthermore, recombination dynamics of excitonic transitions was measured under high-density excitation. An excitation-density-dependent transition of the dominant radiative recombination process from donor-bound excitons to biexcitons was clearly observed in the temporal behavior. In addition, double-exponential decay of biexciton luminescence was observed, which is one of the characteristics of biexciton luminescence at high excitation densities.