Two computational-geometric approaches to linear programming are surveyed. One is based on the prune-and-search paradigm and the other utilizes randomization. These two techniques are quite useful to solve geometric problems efficiently, and have many other applications, some of which are also mentioned.

This paper describes a mixed mode circuit simulation by the direct and relaxation-based methods with dynamic network partitioning. For the efficient circuit simulation by the direct method, the algorithms with circuit partitioning and latency technique have been studied. Recently, the hierarchical decomposition and latency and their validities have been researched. Network tearing techniques enable independent analysis of each subnetwork except for the local datum nodes. Therefore, if the local datum nodes are also torn, each subnetwork is separated entirely. Since the network separation is based on relaxation approach, the implementation of the separation technique in the circuit simulation by the direct method corresponds to performing the mixed mode simulation by the direct and relaxation-based methods. In this paper, a dynamic "network separation" technique based on the tightness of the coupling between subnetworks is suggested. Then, by the introduction of dynamic network separation into the simulator SPLIT with hierarchical decomposition and latency, the mixed mode circuit simulator, which selects the direct method or the relaxation method and determines the block size of the latent circuit dynamically and suitably, is constructed.

A file transmission net N is a directed communication net with vertex set V and arc set B such that each arc e has positive cost ca(e) and each vertex u in V has two parameters of positive cost cv(u) and nonnegative integral demand d(u). Some information to be distributed through N is supposed to have been written in a file and the written file is denoted by J, where the file means an abstract concept of information carrier. In this paper, we define concepts of file transfer, positive demand vertex set U and mother vertex set M, and we consider a problem of distributing d(v) copies of J through a file transfer on N from a vertex v1 to every vertex v in V. As a result, for N such that MU, we propose an O(nm+n2 log n) algorithm, where n=|V| and m=|B|, for synthesizing a file transfer whose total cost of transmitting and making copies of J is minimum on N.

This paper presents a new algorithm for finding the kth-shortest paths between a specified pair of vertices in a directed graph with arcs having non-negative costs.

In this paper, a methodology for designing the architecture of the processor array for wide class of image processing algorithms is proposed. A concept of spatially expanding the SFG description which enables us to handle the problem as merely one-dimensional signal processing is used in constructing the methodology. Problem of I/O interface which is critical in real-time processing is also considered.

The erosion of contact metal, which determines the life of contacts in the telephone switching system, is proportional to the arc energy. The equations for arc voltage, arc current, arc duration time and number of arcs are expressed explicitly in terms of circuit parameters and contact properties, and the expression is derived for arc energy that accompanies a single operation of contact closure. Contact erosion is consistent with the calculated arc energy. The erosion rate at closure is estimated based on the measured contact-erosion volume and the calculated arc energy. Arc energy at contact closure becomes as large as that at contact break if the cable is long or the supply voltage is high. This expression in combination with the expression for contact break enabled us to perform contact life design, which is indispensable for maintenance administration of telephone switching systems.

In this paper, optimal static load balancing in a tree hierarchy network that consists of a set of heterogeneous host computers is considered. It is formulated as a nonlinear optimization problem. We study the effects of the link communication time on the optimal link flow rate (i.e., the rate at which a node forwards jobs to other nodes for remote processing), the optimal node load (i.e., the rate at which jobs are processed at a node), and the optimal mean response time, by parametric analysis. We show that the entire network can be divided into several independent sub-tree networks with respect to the link flow rates and node loads. We find that the communication time of a link has the effects only on the link flow rates and the loads on nodes that are in the same sub-tree network. The increase in the communication time of a link causes the decrease in the link flow rates of its descendant nodes, its ancestor nodes and itself, but causes the increase in the link flow rates of other nodes in the same sub-tree network. It also causes the increase in the loads of its descendant nodes and itself, but causes the decrease in the loads of other nodes in the same sub-tree network. In general, it causes the increase in the mean response time.

This paper describes a perspective on Personal Communicatoins Services (PCS) and technological trends. It takes into consideration rules pertaining to the use of PCS for mobile radio communication and countermeasures to cope with the huge increase in PCS subscribers. In this paper, PCS network structures, inter-regional roaming, microcell structure, radio access and channel access methods are also covered as PCS technologies. Furthermore, trends in domestic and international standards are also described. Although these technologies present many difficulties, we believe that they will be overcome and PCS services will be introduced in the near future.

The objective of this work is to demonstrate a new hierarchical timing analysis technique for multi-phase clocked designs with feedback loops including level sensitive latches. By using this technique, large synchronous designs can be analyzed accurately without loop breaking.

A new indexing technique for rapid evaluation of nested query on composite object is propoced, reducing the overall cost for retrieval and update. An extended B+ tree is introduced in which object identifier (OID) to be searched and path information usud for update of index record are stored in leaf node and subleaf node, respectively. In this method, the retrieval oeration is applied only for OIDs in the leaf node. The index records of both leaf and subleaf nodes are updated in such a way that the path information in the subleaf node and OIDs in the leaf node are reorganized by deleting and inserting the OIDs. The techniaue presented offers advantages over currently related indexing techniques in data reorganization and index allocation. In the proposed index record, the OIDs to be reorganized are always consecutively provided, and thus only the record directory is updated when an entire page should be removed. In addition, the proposed index can be allocate to a path with the length greater than 3 without splitting the path. Comparisons under a variety of conditions are given with current indexing techniques, showing improved performance in cost, i.e., the total number of pages accessed for retrieval and update.

We propose a hierarchical multi-layer global router for Sea-Of-Gates VLSI's, which is different from the conventional global routers, in that routing and layering are executed simultaneously. The main problems to be solved in the global routing for a multi-layer VLSI are which wire segments are laid out on upper layers and how they are connected to terminals located on lower layers. The main objective is to minimize the maximum of local congestions of all layers. We solve these problems in a hierarchical manner by routing from upper layers to lower layers.

An improved array architecture to realize fast access, low power dissipation, and wide operating margin, for the 16 Mbit DRAM is proposed. A high speed access is obtained by the fully embedded sense drive scheme for the RAS access time (tRAC), and the special page mode with the hierarchical I/O data bus lines and multi-purpose-register (MPR) for the column address access time (tCAA). A low power dissipation and wide operating margin are obtained by the improved twisted-bit-line (TBL) architecture with double dummy canceling. The 16 Mb DRAM using these architectures has 38 ns tRAC, 14 ns tCAA and 75 mA power dissipation at the typical condition.

This paper describes the performance evaluation of the Translation Look-aside Buffer (TLB) for highly integrated microprocessors, especially concerning the TLB in the SPARC Reference MMU specification. The analysis covers configurations, the number of entries, and replacement algorithms for the instruction TLB and the data TLB, which are assumed to be practically integrated on one die. We also present performance improvement using a Page Table Cache (PTC). We evaluate some types of TLB configurations with software simulation and excute the Systems Performance Evaluation Cooperative (SPEC) programs.

As the telecommunications network provides a greater variety of services and more rapidly incorporates new technologies, it has become important to ensure modular functional growth of the network. As a part of the endeavor toward this goal, this paper discusses the functional architecture of a network, which defines the functional elements and the interfaces between them. Object-oriented paradigm is applied to develop this architecture. Because the objects which will be made in the software will become too numerous to manage, it is proposed to make a functional element out of a set of objects, grouped together on the basis of functional affinity, plus an interface object. A functional element communicates with other functional elements only via its interface object. The physical location of each functional element can be hidden from other functional elements by the support of distributed processing environment. To secure real-time performance, communications between functional elements are classified into two classes: direct and indirect communications. In order to examine technical feasibility an evaluate the various alternatives of functional architecture, and experimental system called EONS (Experimental Object-oriented Nodal System) was developed. The hardware equipment of EONS consists of a switching unit and workstations. The functional architecture implemented in the EONS is structured in two layers: hardware-independent, logical control layer and hardware-dependent, resource control layer. As an example of service application, universal personal telecommunication (UPT) service has been implemented.

We study the most appropriate network architecture for constructing FTTH (Fiber To The Home) networks. We conclude that the Single Star network is the most advantageous for supporting the various services required by subscribers who use broadband signal such as B-ISDN (Broadband-Integrated Services Digital Network). We also study high fiber count cable and low-loss connector which are needed for this network and clarify their requirements. We also show the cable structure, connector structure and connection loss reduction method, which satisfy these requirements. We describe a 4,000-fiber cable with a new structure, a 1,000-fiber one-touch connector, a 40-fiber unit connector and TEC-fiber (Thermally-diffused Expanded Core fiber) which reduces connection loss.

This paper proposes a next-generation narrow-band ISDN (N-ISDN), including a suitable network and network node architecture. The proposed N-ISDN allows every subscriber to use H0/HI-class calls as easily as present telephone calls, and could rapidly expand ISDN services to all the subscribers of a public network. The present status of ISDN is first analyzed then the need for popularization of H0/HI-call services is discussed. The proposed key technologies to popularize HO/HI services are (1) on-chip integration of ISDN switching systems, (2) distribution of small on-chip switching systems over the subscriber switching area, (3) H0-based trunk circuit networks using H0 on-chip switching systems and (4) efficient and flexible call management for 64-kb/s basic-class calls. An estimation of hardware volume of switching nodes is used to show that the proposed architecture is more economical than other possible alternatives, i.e. conventional ISDN and B-ISDN.

This paper proposes a hierarchical Digital Signal Processor (DSP) Code Generator VIRGO for large scale general signal processing algorithms. Hierarchical structured Vectorized Signal Flow Graph (V-SFG) description is used as input specifications. Ths DSP independent optimization procedure for both the program size and the execution time is performed each module by each hierarchically with regard to operation order, memory assignment and register allocation. The efficient code generation is demonstrated by comparing both instruction steps and dynamic steps of a practical ADPCM encoder/decoder with a conventional method.

The establishment of an intelligent network service operation architecture is important for facilitating development and integration of service operation systems. To do this, the basic concepts and goals of service operation items must first be clarified. Then, the necessary procedures as well as the required data on the behaviors of customers, operators and operation systems must be described. These various points are discussed based on an operation study methodology.

A learning algorithm for neural controllers based on random search is proposed. The method presents an attractive feature in comparison with the learning of neural controllers using the standard backpropagation method. Namely, in this approach the identification of the unknown plant becomes unnecessary because the parameters of the controller are determined by a trial and error process. This is a favorable feature particularly in cases in which the characteristics of the system are complicated and consequently the identification is difficult or impossible to perform at all. As application examples, the learning control of the pendulum system and the maze problem are shown.

Based on the Fornasini-Marchesini second model, an efficient algorithm is developed to derive the characteristic polynomial and the inverse of the system matrix from the state-space parameters. As a result, the external description of the Fornasini-Marchesini second model is clarified. A technique for designing 2-D recursive digital filters in the frequency domain is then presented by using the Fornasini-Marchesini second model. The resulting filter approximates both magnitude and group delay specifications and its stability is always guaranteed. Finally, three design examples are given to illustrate the utility of the proposed technique.