A Generalized Hypercube Network (GHNet) with shared channels which requires only one fixed-wavelength transmitter and r(m-1) fixed-wavelength receivers per node is proposed. The proposed network topology reduces not only the number of transmitters per node but also the number of WDM channels required to service the same number of nodes compared with the GHNet with dedicated channels by sharing the available WDM channels, while it maintains the same channel efficiency as the GHNet with dedicated channels. The proposed network topology may be preferred in a situation where the number of available WDM channels and the cost of the transmitter may cause a major restriction on the lightwave network construction. For performance analysis, the network capacity and the mean queueing delay for the proposed network topology are obtained. Also, the performance measures of the proposed GHNet with shared channels are compared with those of the ShuffleNet with shared channels.

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.

By adding some functions to memories, highly parallel computation may be realized. We have proposed memory-based parallel computation models, which uses a new functional memory as a SIMD type parallel computation engine. In this paper, we consider models with communication between the words of the functional memory. The memory-based parallel computation model consists of a random access machine and a functional memory. On the functional memory, it is possible to access multiple words in parallel according to the partial match with their memory addresses. The cube-FRAM model, which we propose in this paper, has a hypercube network on the functional memory. We prove that PSPACE is accelerated to polynomial time on the model. We think that the operations on each word of the functional memory are, in a sense, the essential ones for SIMD type parallel computation to realize the computational power.