Takanobu BABA Norihito SAITOH Takahiro FURUTA Hiroshi TAGUCHI Tsutomu YOSHINAGA
We have designed and implemented a simple yet powerful declarative synchronization mechanism for a paralle object-oriented computation model. The mechanism allows the user to control multiple message reception, specify the order of message reception, lock an invocation, and specify relations as invocation constraints. It has been included in a parallel object-oriented language, called A-NETL. The compiler and operating system have been developed on a total architecture, A-NET (Actors NETwork). The experimental results show that (i) the mechanism allows the user to model asynchronous events naturally, without losing the integrity of described programs; (ii) the replacement of the mechanism with the user's code requires tedious descriptions, but gains little performance enhancement, and certainly loses program readability and integrity; (iii) the mechanism allows the user to shift synchronous programs to asynchronous ones, with a scalable reduction of execution times: an average 20.6% for 6 to 17 objects and 46.1% for 65 objects. These prove the effectiveness of the proposed synchronization mechanism.
Eriko TAKEDA Toshikazu NISHINO Kazumasa TAKAGI
The relationship between the flux-trapping phenomenon and the device-structure of a SQUID has been studied using three types of SQUIDs; a SQUID with a guard-ring, a SQUID with a moat, and a SQUID without these structures. The change in the voltage-flux characteristics of the SQUIDs due to the flux-trapping are measured. For the measurements, an acceleration of the flux-trapping is realized by applying a magnetic field during cooling of the SQUIDs. From the measured results, the SQUID with the guard-ring and that with the moat can reject tha external magnetic field more effectively than the SQUID without these structures. The reason of the difference in the rejection of the external magnetic field is thought to be the existence of superconducting closed loops. However, the flux-trapping of the SQUID with the guard-ring and that with the moat occur more easily than the flux-trapping of the SQUID without these structures for the cooling under the finite magnetic field. Therefore, the moat structure and the guard-ring structure need a higher-grade magnetic shielding for a practical use.
Toshiaki KURI Katsutoshi TSUKAMOTO Norihiko MORINAGA
In coherent optical space communication systems, the phase noise generated from high power laser diodes and the polarization axis mismatch between transmitter and receiver are the serious problem. In this paper, a novel coherent optical space communication system, called optical polarization azimuth modulation (POLAM)/heterodyne detection system is newly proposed, and its system performance is theoretically investigated. It is clarified that the POLAM system can perfectly remove the laser phase noise, is actually insensitive to the polarization axis mismatch, and can provide the remarkable performance improvement compared to a conventional optical frequency modulation system.
Hisashi KADO Gen UEHARA Hisanao OGATA Hideo ITOZAKI
This paper describes a SQUID magnetometer and the measurement of small signals. It also describes the current state of SQUID technology developed in the SSL project.
Junji SAKURABA Mamoru ISHIHARA Seiji YASUHARA Kazunori JIKIHARA Keiichi WATAZAWA Tsuginori HASEBE Chin Kung CHONG Yutaka YAMADA Kazuo WATANABE
Cryocooler cooled superconducting magnets using Bismuth based high-Tc current leads have been successfully demonstrated. The magnets mainly consisted of a superconducting coil, current leads and a radiation shield which are cooled by a two stage Gifford-McMahon cryocooler without using liquid helium. Our first liquid helium-free 4.6 T (Nb, Ti)3Sn superconducting magnet with a room temperature bore of 38 mm operated at 11 K has recorded a continuous operation at 3.7 T for 1,200 hours and total cooling time over 10,000 hours without trouble. As a next step, we constructed a (Nb, Ti)3Sn liquid helium-free superconducting magnet with a wider room temperature bore of 60 mm. The coil temperature reached 8.3 K in 37 hours after starting the cryocooler. The magnet generated 5.0 T at the center of the 60 mm room temperature bore at an operating current of 140 A. An operation at a field of 5 T was confirmed to be stable even if the cryocooler has been stopped for 4 minutes. These results show that the liquid helium-free superconducting magnets can provide an excellent performance for a new application of the superconducting magnet.
Eikoh CHIDA Hiroki SHIZUYA Takao NISHIZEKI
A near-ring is an extended notion of a usual ring. Therefore a ring is a near-ring, but the converse does not necessarily hold. We investigate in this paper one-way functions associated with finite near-rings, and show that if there exists a one-way group homomorphism, there exists a one-way non-ring near-ring homomorphism (Theorem 1); if there exists a one-way ring homomorphism (Theorem 2). Further, we introduce a discrete logarithm problem over a finite near-ring, and show that the integer factoring is probabilistic polynomial-time Turing equivalent to a modified version of this problem (Theorem 3). Theorem 1 implies that under some standard cryptographic assumption, there is an affirmative but trivial solution to the extended version of the open question: Is there an encryption function f such that both f(x+y) and f(xy) are efficiently computed from given f(x) and f(y) ?
Kazuo TORAICHI Takahiko HORIUCHI
In order to realize a continuous-time system model in digital computers, we must construct a discrete-time system model simulating the continuous-time processes in some characteristic aspect. Though many discretization methods have been proposed, they do not necessarily provide a discrete-time system in which input, state and output are identical with the sampled values of the original continuous-time system. The isomorphism discretization that all of the input, state and output of a continuous-time system can be recovered from the corresponding discrete-time system is crucial for our analysis. This paper aims at guaranteeing the isomorphism between a continuous- and a discrete-time system models (fluency system model) which were proposed by the authors. The isomorphism of input space had been already shown in the previous works by one of the authors. In this paper, by showing the isomorphism of the state function and output spaces, the aim will be achieved.
This paper presents a linear time algorithm for testing whether or not there is a path
In this paper we investigate the AM languages that seem to be located outside NP co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in ΔP2 AM co-AM but is unlikely to be in NP co-NP, and that GH is in ΔP2 AM but is unlikely to be in NP co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those languages: Any language that is polynomial time truth-table reducible to GIP is in AM co-AM; GIP is in co-SZK if SZK co-SZK is closed under conjunctive polynomial time bounded-truth-table reducibility; Both GIP and GH are in DP. Here DP is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.
High speed simulation of neural networks can be achieved through parallel implementations capable of exploiting their massive inherent parallelism. In this paper, we show how this inherent parallelism can be effectively exploited on parallel data-driven systems. By using these systems, the asynchronous parallelism of neural networks can be naturally specified by the functional data-driven programs, and maximally exploited by pipelined and scalable data-driven processors. We shall demonstrate the suitability of data-driven systems for the parallel simulation of neural networks through a parallel implementation of the widely used back propagation networks. The implementation is based on the exploitation of the network and training set parallelisms inherent in these networks, and is evaluated using an image data compression network.
This paper considers the problem of finding a largest common subgraph of graphs, which is an important problem in chemical synthesis. It is known that the problem is NP-hard even if graphs are restricted to planar graphs of vertex degree at most three. By the way, a graph is called an almost tree if E(B)V(B)+ K holds for every block B where K is a constant. In this paper, a polynomial time algorithm for finding a largest common subgraph of two graphs which are connected, almost trees and of bounded vertex degree. The algorithm is an extension of a subtree isomorphism algorithm which is based on dynamic programming. Moreover, it is shown that the degree bound is essential. That is, the problem of finding a largest common subgraph of two connected almost trees is proved to be NP-hard for any K0 if degree is not bounded. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem.
Chan-Hyun YOUN Yoshiaki NEMOTO Shoichi NOGUCHI
In this paper, we discuss to the intermedia synchronization problems for high speed multimedia communication. Especially, we described how software synchronization can be operated, and estimated the skew bound in CNV when considering the network delay. And we applied CNV to the intermedia synchronization and a hybrid model (HSM) is proposed. Furthermore, we used the statistical approach to evaluate the performance of the synchronization mechanisms. The results of performance evaluation show that HSM has good performance in the probability of estimation error.
Jinhui CHAO Kenji MINOWA Shigeo TSUJII
The self-organization rule of planar neural networks has been proposed for learning of 2D distributions. However, it cannot be applied to 3D objects. In this paper, we propose a new model for global representation of the 3D objects. Based on this model, global topology reserving self-organization is achieved using parallel local competitive learning rule such as Kohonen's maps. The proposed model is able to represent the objects distributively and easily accommodate local features.
This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.
Akira USAMI Hideki FUJIWARA Takahisa NAKAI Kazunori MATSUKI Tsutomu TAKEUCHI Takao WADA
A laser/microwave method using two lasers of different wavelengths for carrier excitation is proposed to evaluate Si surfaces. These constitute a He-Ne laser (wavelength=633 nm, penetration depth=3 µm) and a YAG laser (wavelength=1060 nm, penetration depth=500 µm). Using a microwave probe, the amount of excited carriers can be detected. The carrier concentration is mainly dependent on the condition of the surface when carriers are excited by the He-Ne laser, as well as on the condition of the bulk region when carriers are excited by the YAG laser. Microwave intensities detected under the He-Ne and the YAG lasers illumination are referred to as the surface-recombination-velocity-related microwave intensity (SRMI) and the bulk-related microwave intensity (BRMI), respectively. The difference between SRMI and BRMI is called relateve SRMI (R-SRMI), and is closely related to the condition of the surface and surface active region. We evaluate the surfaces of the samples after plasma and wet etching to remove the photoresist layer. And we evaluate the surfaces of the samples after heat or HF treatment which is done to recover the damage introduced by plasma etching. It was found that the R-SRMI method is better suited to surface evaluation than conventional lifetime measurements.
Masaya ICHIMURA Yukihisa MORIGUCHI Akira USAMI Takao WADA
A Ge/Si structure grown by chemical vapor deposition (CVD) is angle-lapped and characterized by the micro-Raman spectroscopy. Near the interface, the phonon mode due to the Si-Ge bond is clearly observed, which indicates that a SiGe alloy is formed by the solid-phase interdiffusion at the interface. The thickness of the interfacial alloy layer is about 0.2 µm. Amount of residual strain is estimated by comparing the measured phonon frequencies with those predicted from the composition profie, but the shift due to the residual strain is not appreciable. Both the interdiffusion at the interface and the nearly complete relaxation of the lattice mismatch are attributed to the high growth temperature of the CVD sample.
Akira USAMI Hideki FUJIWARA Noboru YAMADA Kazunori MATSUKI Tsutomu TAKEUCHI Takao WADA
This paper describes a new evaluation technique for Si surfaces. A laser/microwave method using two lasers of different wavelengths for carrier injection is proposed to evaluate Si surfaces. With this evaluation system, the effect of impedance mismatching between the microwave probe and the Si wafer can be eliminated. These lasers used in this experiment are He-Ne (wavelength633 nm, penetration depth3 µm) and YAG lasers (wavelength1060 nm, penetration depth500 µm). Using a microwave probe, the amount of injected excess carriers can be detected. These carrier concentrations are mainly dependent on the condition of the surface, when carriers are excited by the He-Ne laser, and the condition of the bulk region, when carriers are excited by the YAG laser. We refer to microwave intensities detected by the He-Ne and YAG lasers as the surface-recombination-velocity-related microwave intensity (SRMI) and bulk-related microwave intensity (BRMI), respectively. We refer to the difference between SRMI and BRMI as relative SRMI (R-SRMI), which is closely related to the surface condition. A theoretical analysis is performed and several experiments are conducted to evaluate Si surfaces. It is found that the R-SRMI method is better suited to surface evaluation then conventional lifetime measurements, and that the rdliability and reproducibility of measurements are improved.
Lingas developed an NC algorithm for subgraph isomorphism for connected graphs of bounded separator and bounded valence. We present an NC algorithm for computing canonical forms of graphs of bounded separator by using the similar technique.
It is known that the problem of finding a largest common subgraph is NP-hard for general graphs even if the number of input graphs is two. It is also known that the problem can be solved in polynomial time if the input is restricted to two trees. In this paper, a randomized parallel (an RNC) algorithm for finding a largest common subtree of two trees is presented. The dynamic tree contraction technique and the RNC minimum weight perfect matching algorithm are used to obtain the RNC algorithm. Moreover, an efficient NC algorithm is presented in the case where input trees are of bounded vertex degree. It works in O(log(n1)log(n2)) time using O(n1n2) processors on a CREW PRAM, where n1 and n2 denote the numbers of vertices of input trees. It is also proved that the problem is NP-hard if the number of input trees is more than two. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem of finding a largest common subtree of three trees.