This paper deals with the problem of assigning tasks to the processors of a multiprocessor system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. In this paper, we propose a network flow approach for the task assignment problem in homogeneous hypercube networks, i.e., hypercube networks with functionally identical processors. The task assignment problem for an n-dimensional homogeneous hypercube network of N (=2n) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M3 log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.

The subject of the paper is to analyze time complexity of the minimum modification problem in the Horn clause propositional logic. Given a set H of Horn clauses and a query Q in propositional logic, we say that Q is provable over H if and only if Q can be shown to be true by repeating Modus Ponens among clauses of H. Suppose that Q is not provable over H, and we are going to modify H and Q into H and Q , respectively, such that Q is provable over H . The problem of making such modification by minimum variable deletion (MVD), by minimum clause addition (MCA) or by their combination (MVDCA) is considered. Each problem is shown to be NP-complete, and some approximation algorithms with their experimental evaluation are given.

New methods are needed for accessing very large information services. This paper proposes the use of a user model neural network to allow better access to a news service. The network is constructed on the basis of articles read, and articles marked as rejected. It adapts over time to better represent the user's interests and rank the articles supplied by the news service. Using an augmented keyword search we can also search for articles using keywords in conjunction with the user model neural network. Trials of the system in a USENET news environment show promising results for the use of this approach in information retrieval.

The subject of the paper is to analyze time complexity of the minimum axiom set problem (MASHC) in the Horn clause propositional logic. MASHC is defined by "Given a set H of Horn clauses and a query Q, all in propositional logic, such that Q is provable over H, find an axiom set of minimum cardinality, HH, with respect to Q, where Q is provable over H if and only if Q can be shown to be true by repeating Modus Ponens starting from clauses of H under the assumption that all of them are originally assumed to be true". If Q is provable over H then H is called an axiom set (with respect to Q). As stated in the definition of MASHC, detecting if Q is provable over H is required. This leads us to a problem, called the provability detecting problem (PDPHC), defined by "Given a set H of Horn clauses and a query Q in propositional logic, determine if Q is provable over H". First an O(σ) algorithm BFSHC for PDPHC is given based on the breadth-first search, where σ is the formula size of a given set of Horn clauses. For MASHC, it is shown that the problem is NP-complete, and an O(σ) approximation algorithm FMAS is given. Its experimental evaluation is also presented.

By close analogy of annealing for solids, we devise a new algorithm, called APS, for the time evolution of both the state and the synapses of the Hopfield's neural network. Through constrainedly random perturbation of the synapses of the network, the evolution of the state will ignore the tremendous number of small minima and reach a good minimum. The synapses resemble the microstructure of a network. This new algorithm anneals the microstructure of the network through a thermal controlled process. And the algorithm allows us to obtain a good minimum of the Hopfield's model efficiently. We show the potential of this approach for optimization problems by applying it to the will-known traveling salesman problem. The performance of this new algorithm has been supported by many computer simulations.

A new approach is proposed to evaluate total electromagnetic noise radiated from a printed circuit board (PCB), and a result of experimental verification is given. The purpose is to represent the total radiation noise by summing up noises from elemental sources on a PCB, such as signal traces or ICs. Each of the elemental noise is calculated by an a priori noise model for each component of a PCB. Parameters of each noise model should be determined experimentally. Radiation sources on a digital PCB were found to be not only signal traces between ICs, but also package-side loops each of which is composed of an IC and a decoupling capacitor. Radiation noises from these two kinds of sources were evaluated separately. Experimental PCBs, which are two-layer PCBs mounting a few high-speed CMOS (HC) ICs, were prepared and radiation power from them was measured. Each PCB has a ground plane on one side, which simulates an internal ground plane in a multilayer PCB, and signal traces on it have a configuration of a microstrip transmission line. Electromagnetic noise caused by a high-speed CMOS gate is radiated impulsively during transition time as short as about 10ns. No significant interference was found between the noises from separate traces because each of the noise is impulsive and rarely overlaps each other. It is concluded that the total radiated power is represented by a simple sum of radiations from each traces without any interference to be taken into account.

For the efficient circuit simulation by the direct method, network tearing and latency techniques have been studied. This letter describes a circuit simulator SPLIT with hierarchical decomposition and latency. The block size of the latent subcircuit can be determined dynamically in SPLIT. We apply SPLIT to the MOS circuit simulation and verify its availability.

First, a number of issues pertaining to analog VLSI implementation of Backpropagation (BP) and Deterministic Boltzmann Machine (DBM) learning algorithms are clarified. According to the results from software simulation, a mismatch between the activation function and derivative generated by independent circuits degrades the BP learning performance. The perfomance can be improved, however, by adjusting the gain of the activation function used to obtain the derivative, irrespective of the original activation function. Calculation errors embedded in the circuits also degrade the learning preformance. BP learning is sensitive to offset errors in multiplication in the learning process, and DBM learning is sensitive to asymmetry between the weight increment and decrement processes. Next, an analog VLSI architecture for implementing the algorithms using common building block circuits is proposed. The evaluation results of test chips confirm that synaptic weights can be updated up to 1 MHz and that a resolution exceeding 14 bits can be attained. The test chips successfully perform XOR learning using each algorithm.

ATM cross-connect systems, which will be used for provisioning virtual paths (i.e. logical direct connections between exchanges) in future broadband transport networks, simplify network configuration and yield increased routing and capacity allocating flexibility. This paper describes the design of a large capacity ATM cross-connect system that has a multi-stage network structure which requires only one type of switch module. The capacity of the proposed system can be easily increased without service interruptions. To realize cell sequence integrity, a time stamp is added to the self-routing tag. Required time stamp length and efficient module size are discussed.

Anechoic chambers have been effectively used for microwave propagation, electromagnetic interference (EMI) and immunity testing. The electromagnetic compatibility (EMC) problem has recently become serious and many of these chambers have been constructed. The results of a questionnaire survey sent to anechoic chamber manufacturers are described that a total of 450 anechoic chambers have been constructed in Japan since 1964. Twenty years ago the purpose of the chambers was microwave propagation research, but more than 50 each year have recently being built for EMC/EMI and immunity testing. Their size has gradually been reduced by the use of absorbing materials such as ferrite with dielectric materials. The lowest frequency of most chambers is 30MHz for the 3 m method of site attenuation.

It is important to develop methods of measuring radiated electromagnetic interference level that will produce identical results at all measuring locations. We have considered a number of problems which prevent the achievement of identical results, and proposed some solutions. However, agreement of measurement values adequate for practical purposes has not been achieved. After our successive studies, we finally became aware that there is a causal relationship with changes in the line-to-ground impedance of the power supply. It is presumed that power cables of AC-powered devices operate as antenna elements that produce emission. Thus changes in the power line-to-ground impedance cause variations in the radiation efficiency to produce a different EMI level. We therefore made plans to measure the values of line-to-ground impedance at the AC power outlet for the frequency range of 100kHz to 500MHz at various locations where measurements are made of EMI from EUT (Equipment Under Test). The impedance varies greatly between 6ohms and 2 k-ohm, not only according to the frequency, but also according to the measurement location. In such cases, the EMI level shows a different value even with the same EUT, and it usually increases-especially for vertical polarization. We have developed a new type of LISN (Line Impedance Stabilization Network or Artificial Mains Network) to stabilize the power line-to-ground impedance to get consistent measurement conditions. The LISN consists of feed-through capacitors and an disk type RF resistor. The measurements confirm the consistency in the impedance value which is maintained at 50 ohms in the frequency range from 1MHz to 500MHz. Thus the newly developed LISN improves consistency of measurement values at all locations, while it was difficult to obtain good correlation before employing the LISN. We feel confident that incorporation of the method discussed here in the pertinent technical standards of EMI measurements, such as CISPR, would lead to a major improvement in getting consistent measurements values.

This paper presents a survey on bicriteria network optimization problems. When there are two conflicting criteria that evaluate the solution, the bicriteria optimization is to find a solution for which these criteria are both acceptably satisfied. Standard approaches to these problems are to combine these two criteria into an aggregated single criterion. Among such problems, this paper first deals with the case in which the aggregated objective function, denoted h(f1(x), f2(x)), is convex in original two objectives f1(x) and f2(x), and, as its special case, it reviews a strongly polynomial algorithm for the bicriteria minimum-cost circulation problem. It then discusses the case in which h is concave and demonstrates that a parametric approach is effective for this case. Several interesting applications in network optimization that belong to this class are also introduced. Finally we deal with the minimum range problems which seek to find a solution such that weights of the components used in the solution are most uniform. We shall present efficient algorithms for solving these problems arised in network optimization.

In general, dynamic channel assignment has a better performance than fixed channel assignment in a cellular mobile communication system. However, it is complex to control the system and a lot of equipments are required in each cell when dynamic channel assignment is applied to a large service area. Therefore, it is effective to limit the size of the service area in order to correct the defects of dynamic channel assignment. So, we propose an application of dynamic channel assignment to a part of a service area when fixed channel assignment is applied to the remaining part of the area. In the system, the efficiency of channel usage in some cells sometimes becomes terribly low. The system has such a problem to be improved. We show that the rearrangement of the channel allocation is effective on the problem.

Radiation properties of magnetic noise from the harness wires of a spacecraft (GEOTAIL) have been studied experimentally and theoretically. A simulation experiment on the noise radiation using a minimum set of subsystems of the spacecraft has shown that the intensity and the directional patterns of the noise radiation from the wires were largely changed by the existence of a conductive plate near the harness wires. The change in the noise characteristics is explained by eddy currents induced in the conductive plate by the signal current flowing in the wires. The eddy currents distributed in the conductive plate were calculated by the Finite Element analysis Method (FEM). The magnetic flux densities calculated from both the source signal current and its induced eddy currents for the wiring configuration of the simulation experiment have shown to be consistent with the values obtained in the experiment. The results in the present study have provided us an important information on a wiring method to diminish noise radiation from harness wires.

The groupware for new idea generation system, GUNGEN, has been developed. GUNGEN consists of a distributed and cooperative KJ method support system and an intelligent productive work card support system. The system was implemented on a network consisting of a number of personal computers. The distributed and cooperative KJ method is carried out on computers. The ideas proposed by participants are classified into several groups on the basis of similarity and then a conclusion is derived. The intelligent productive work card support system can be used as a multimedia database to refer to the previous data of the distributed and cooperative KJ method.

We present schemes for disseminating information in the n-dimensional hypercube with some faulty nodes/edges. If each processor can send a message to t neighbors at each round, and if the number of faulty nodes/edges is k(kn), then this scheme will broadcast information from any source to all destinations within any consecutive n+[(k+l)/t] rounds. We also discuss the case where the number of faulty nodes is not less than n.

We review the role of optics in interconnects, analog processing, neural networks, and digital computing. The properties of low interference, massively parallel interconnections, and very high data rates promise extremely high performance for optical information processing systems.

We review the role of optics in interconnects, analog processing, neural networks, and digital computing. The properties of low interference, massively parallel interconnections, and very high data rates promise extremely high performance for optical information processing systems.

This paper presents a new connected associative memory neural network. In this network, a threshold function which has two dynamical parameters is introduced. After analyzing the dynamical behaviors and giving an upper bound of the memory capacity of the conventional connected associative memory neural network, it is demonstrated that these parameters play an important role in the recalling processes of the connected neural network. An approximate method of evaluationg their optimum values is given. Further, the optimum feedback stopping time of this network is discussed. Therefore, in our network, the recalling processes are ended at the optimum feedback stopping time whether a state energy has been local minimum or not. The simulations on computer show that the dynamical behaviors of our network are greatly improved. Even though the number of learned patterns is so large as the number of neurons, the statistical properties of the dynamical behaviors of our network are that the output series of recalling processes approach to the expected patterns on their initial inputs.

A chordal ring network is a processor network on which n processors are arranged to a ring with additional chords. We study a distributed leader election algorithm on chordal ring networks and present trade-offs between the message complexity and the number of chords at each processor and between the message complexity and the length of chords as follows:For every d(1dlog* n1) there exists a chordal ring network with d chords at each processor on which the message complexity for leader election is O(n(log(d1)nlog* n)).For every d(1dlog* n1) there exists a chordal ring network with log(d1)nd1 chords at each processor on which the message complexity for leader election is O(dn).For every m(2mn/2) there exists a chordal ring network whose chords have at most length m such that the message complexity for leader election is O((n/m)log n).