Faculty Profiles - FUNABIKI Nobuo

MISC - FUNABIKI Nobuo

Division display 561 - 573 of about 573 ／ All the affair displays >>

A parallel algorithm for traffic control problems in three-stage connecting networks

Nobuo Funabiki, Yoshiyasu Takefuji

Journal of Parallel and Distributed Computing 20 ( 2 ) 236 - 240 1994

Language：English

A parallel heuristic algorithm for traffic control problems in three-stage connecting networks is presented in this paper. A three-stage connecting network consists of an input crossbar switching stage, an intermediate crossbar switching stage, and an output crossbar switching stage. The goal of our algorithm is to quickly and efficiently find a conflict-free switching assignment for communication demands through the network. The algorithm requires n2 × m processing elements for the network composed of n input/output switches and m intermediate switches, where it runs not only on a sequential machine, but also on a parallel machine with maximally n2 × m processors. The algorithm was verified by 1100 simulation runs with the network size from 102 × 7 to 502 × 27. The simulation results show that the algorithm can find a solution in nearly constant time with n2 × m processors. © 1994 Academic Press, Inc.

DOI： 10.1006/jpdc.1994.1022

Scopus

researchmap

A Parallel Algorithm for Time-Slot Assignment Problems in TDM Hierarchical Switching Systems

Nobuo Funabiki, Yoshiyasu Takefuji

IEEE Transactions on Communications 42 ( 10 ) 2890 - 2898 1994

Language：English

This paper presents a parallel algorithm for timeslot assignment problems in TDM hierarchical switching systems, based on the neural network model. The TDM systems are operated. in repetitive frames composed of several Time-Slots. A Time-Slot represents a switching configuration where one packet is transmitted through an I/O line. The goal of our algorithm is to find conflict-free Time-Slot assignments for given switching demands. The algorithm runs on a maximum of n2×m processors for m-Time-Slot problems in n×n TDM systems. In small problems up to a 24×24 TDM system, the algorithm can find the optimum solution in a nearly constant time, when it is performed on n2×m processors. © 1994 IEEE

DOI： 10.1109/26.328959

Scopus

researchmap

A parallel multi-layer channel router on the HVH model

Nobuo Funabaki, Yoshiyasu Takefuji

Parallel Computing 19 ( 1 ) 63 - 77 1993

Language：English

With the advancement of the silicon technology multi-layered VLSI circuits and PCBs (printed circuit boards) have been widely used. Based on the neural network model this paper presents the first parallel algorithm for multi-layer channel routing problems on the HVH model which minimize wiring areas in VLSI circuits and PCBs. The algorithm requires n × m × 2s processing elements for the n-net-m-track-3s-layer problem. The algorithm not only runs on a sequential machine but also on a parallel machine with maximally n × m × 2s processors. The algorithm is verified by solving seven benchmark problems where it finds better solutions than the existing algorithms for 6-12-layer problems in nearly constant time on a parallel machine. © 1993.

DOI： 10.1016/0167-8191(93)90105-T

Scopus

researchmap

Comparisons of Seven Neural Network Models on Traffic Control Problems in Multistage Interconnection Networks

Nobuo Funabiki, Yoshiyasu Takefuji, Kuo Chun Lee

IEEE Transactions on Computers 42 ( 4 ) 497 - 501 1993

Language：English

This paper presents performance comparisons of seven neural network models on traffic control problems in multistage interconnection networks. The decay term, three neuron models, and two heuristics were evaluated. The goal of the traffic control problems is to find conflict-free switching configurations with the maximum throughput. Our simulation results show that the hysteresis McCulloch-Pitts neuron model without the decay term and with two heuristics has the best performance. © 1993 IEEE

DOI： 10.1109/12.214695

Scopus

researchmap

A Neural Network Approach to Topological Via-Minimization Problems

Nobuo Funabiki, Yoshiyasu Takefuji

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 12 ( 6 ) 770 - 779 1993

Language：English

Toooloeical via-minimization (TVM) algorithms in two-layer channels based on the artificial neural network model are presented in this paper. TVM problems require not only assigning wires or nets between terminals without an intersection to one of two layers, but also a minimization of the number of vias, which are the single contacts of nets between two layers. The goal of our algorithms is to embed the maximum number of nets without an intersection. Two types of TVM problems are examined: split rectangular TVM (RTVM) problems and split circular TVM (CTVM) problems. Our algorithms require 3n processing elements for the n-net split RTVM problems, and 5n processing elements for the n-net split CTVM problems. The algorithms were verified by solving seven problems with 20 to 80 nets. The algorithms can be easily extended for more-than-two-layer problems. © 1993 IEEE

DOI： 10.1109/43.229751

Scopus

researchmap

A Parallel Algorithm for Broadcast Scheduling Problems in Packet Radio Networks

Nobuo Funabiki, Yoshiyasu Takefuji

IEEE Transactions on Communications 41 ( 6 ) 828 - 831 1993

A neural network model for finding a near-maximum clique

Nubuo Funabiki, Yoshiyasu Takefuji, Kuo Chun Lee

Journal of Parallel and Distributed Computing 14 ( 3 ) 340 - 344 1992.3

Language：English

A parallel algorithm based on the neural network model for finding a near-maximum clique is presented in this paper. A maximum clique of a graph G is a maximum complete subgraph of G where any two vertices are adjacent. The problem of finding a maximum clique is NP-complete. The parallel algorithm requires n processing elements for an n-vertex graph problem. The algorithm is verified by solving 230 different graph problems. The simulation results show that our computation time on a Macintosh IIfx is shorter than that of two better known algorithms on a Cray 2 and an IBM 3090 while the solution quality is similar. The algorithm solves a near-maximum clique problem in nearly constant time on a parallel machine with n processors. © 1992.

DOI： 10.1016/0743-7315(92)90072-U

Scopus

researchmap

A Parallel Improvement Algorithm for the Bipartite Subgraph Problem

Kuo Chun Lee, Nobuo Funabiki, Yoshiyasu Takefuji

IEEE Transactions on Neural Networks 3 ( 1 ) 139 - 145 1992

Language：English

Since McCulloch and Pitts proposed an artificial neuron model in 1943, several neuron models have been investigated. This paper proposes the first parallel improvement algorithm using the maximum neural network model for the bipartite subgraph problem. The goal of this NP-complete problem is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that our algorithm finds a solution within 200 iteration steps and the solution quality is superior to that of the best existing algorithm. The algorithm is extended for the k-partite subgraph problem, where no algorithm has been proposed. © 1992 IEEE

DOI： 10.1109/72.105427

Scopus

researchmap

A neural network parallel algorithm for clique vertex-partition problems

Nobuo Funabiki, Yoshiyasu Takefuji, Kuo Chun Lee, Yong Beom Cho

International Journal of Electronics 72 ( 3 ) 357 - 372 1992

Language：English

A parallel algorithm based on a neural network model for solving clique vertex-partition problems in arbitrary non-directed graphs is presented in this paper. A clique of a graph G = (V, E) with a set of vertices V and a set of edges E is a complete subgraph of G where any pair of vertices is connected with an edge. A clique vertex-partition problem of a graph G is to partition every vertex in V into a set of disjointed cliques of G. The clique vertex-partition problem with the minimum number of cliques in an arbitrary graph is known to be NP-complete. The algorithm requires nm processing elements for the n vertex m partition problem. A total of 10 different problems with 8 vertex to 300 vertex graphs were examined where the algorithm found a solution in nearly constant time. The circuit diagram of the neural network model is also proposed in this paper. © 1992 Taylor &amp
Francis Ltd.

DOI： 10.1080/00207219208925578

Scopus

researchmap

A Neural Network Parallel Algorithm for Channel Assignment Problems in Cellular Radio Networks

Nobuo Funabiki

IEEE Transactions on Vehicular Technology 41 ( 4 ) 430 - 437 1992

Language：English

A parallel algorithm for channel assignment problems in cellular radio networks is presented in this paper. The channel assignment problem involves not only assigning channels or frequencies to each radio cell, but also satisfying frequency constraints given by a compatibility matrix. The proposed parallel algorithm is based on an artificial neural network composed of nm processing elements for an n-cell-m-frequency problem. The algorithm runs not only on a sequential machine but also on a parallel machine with up to a maximum of nm processors. The algorithm was tested by solving eight benchmark problems where the total number of frequencies varied from 100 to 533. The algorithm found the solutions in nearly constant time with nm processors. The simulation results showed that the algorithm found better solutions than the existing algorithm in one out of eight problems. © 1992 IEEE

DOI： 10.1109/25.182594

Scopus

researchmap

A Parallel Algorithm for Channel Routing Problems

Nobuo Funabiki, Nobuo Funabiki, Yoshiyasu Takefuji

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 11 ( 4 ) 464 - 474 1992

Language：English

A parallel algorithm for channel routing problems is presented in this paper. The channel routing problem is very important in the automatic layout design of VLSI circuits and printed circuit boards. The problem is to route the given interconnections between two rows of terminals on a multilayer channel where the channel area must be minimized. Although several algorithms have been proposed for two-layer problems, two-Iayer-and-over-the-cell problems, and three-layer problems, the current advancement of VLSI chip technology allows us to use four layers composed of two metal layers and two polysilicon layers for routing in a chip. The goal of the proposed parallel algorithm is to find the near-optimum routing solution for the given interconnections in a short time. The algorithm is applied for the four-layer channel routing problems where it requires n × m × 2 processing elements for the n-netm-track problem. The algorithm has three advantages over the conventional algorithms: 1) it can be easily modified for accommodating more than four-layer problems, 2) it runs not only on a sequential machine but also on a parallel machine with maximally n ×m × 2 processors, and 3) the program size is very small. The algorithm is verified by solving seven benchmark problems where the algorithm finds routing solutions in a nearly constant time with n × m × 2 processors. © 1992 IEEE

DOI： 10.1109/43.125094

Scopus

researchmap

A Parallel Algorithm for Allocation of Spare Cells on Memory Chips

Nobuo Funabiki, Yoshiyasu Takefuji

IEEE Transactions on Reliability 40 ( 3 ) 338 - 346 1991.8

In manufacturing memory chips, Redundant Random Access Memory (RRAM) technology has been widely used because it not only provides repair of faulty cells but also enhances the production yield. RRAM has several rows and columns of spare memory cells which are used to replace the faulty cells. The goal of our algorithm is to find a spare allocation which repairs all the faulty cells in the given faulty-cell map. The parallel algorithm requires In processing elements for the n x n faulty-cell map problem. The algorithm is verified by many simulation runs. Under the simulation the algorithm finds one of the near-optimum solutions in a nearly constant time with 0(n) processors. The simulation results show the consistency of our algorithm. The algorithm can be easily extended for solving rectangular or other shapes of fault map problems. Reader Aids - Purpose: Present a new algorithm Special math needed for explanations: Probability Special math needed to use results: None Results useful to: Reliability theoreticians and analysts. © 1991 IEEE

DOI： 10.1109/24.85454

Scopus

researchmap

A NEURAL NETWORK APPROACH TO BROADCASTING IN MULTIHOP PACKET RADIO NETWORKS

N FUNABIKI, Y TAKEFUJI, KC LEE, YB CHO, T KUROKAWA, H AISO

1991 IEEE INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS, VOLS 1-3 2540 - 2545 1991

　 PREV - NEXT 　

< FUNABIKI Nobuo >

MISC - FUNABIKI Nobuo