This paper presents the solution of the following optimization problem that appears in the design of double-loop structures for local networks and also in data memory, allocation and data alignment in SIMD processors.

We consider in this paper the (d,k) problem for directed graphs: to maximize the number of vertices in a digraph of degree d and diameter k. For any values of d and k, we construct a graph with a number of vertices larger than (d 2-1)/d2 times the (non-attainable) Moore bound. In particular, this solves the (d,k) digraph problem for k=2. We also show that these graphs can be obtained as line digraph iterations and that this technique provides us with a simple local routing algorithm for the corresponding networks.

In this paper we compare the effective bandwidth in a multiprocessor with shared memory using as interconnection networks the crossbar or the multiple-bus. We consider a system with N processors and N memory modules, in which the processor requests to the memory modules are independent and uniformly distributed random variables. We consider two cases: in the first the processor makes another request immediately after a memory service, and in the second there is some internal processing time.