Generalized linear recursive networks: topological and routing properties

This paper presents a methodology for generalizing the class of linear recursive networks (LRN) reported by Hsu et al. [IEEE Trans Parallel Distrib Syst 1997; 8(7)]. The proposed generalization relaxes the restriction on the number of isomorphic subgraphs of LRNs, which is at most 1 by Hsu et al. [IEEE Trans Parallel Distrib Syst 1997; 8(7)]. Hence, our methodology permits the design of a communication topology of size n which satisfies the linear recurrence equation G_n(A)=a₁G_n−1(A)∪a₂G_n−2(A)∪?∪a_kG_n−k(A), with a_j being any non-negative integer for each j∈{1,2,…,k} and a₁>0. In addition, we address the problem of routing of messages in an generalized linear recursive network (GLRN). The paradigm of Fibonacci cubes (FCs) is used to demonstrate the proposed technique. FCs were introduced recently as an attractive alternative to the well-known hypercube model for interconnection networks.A generalized FC, referred to as a “Fibonacci graph” (FG) of size n, is composed of an arbitrary number of such graphs of size n−1 and size n−2.The structural advantage of GLRNs, in general, and FG, in particular, manifests itself in the following ways:

1.

They allow more choices to construct systems of various sizes.

2.

They emulate other topologies, such as hypercubes, trees, rings and meshes very efficiently.

The results of this paper have important applications e.g. in multitasking and job scheduling where a job is decomposed into a set of tasks and assigned to a subset of processors with specified interconnection topology.