This paper presents a family of algorithms for producing, from ( upsilon /sub 0/, upsilon /sub 1/, ..., upsilon /sub n-1/), all initial prefixes x/sub i/= upsilon /sub 0/ theta upsilon /sub 1/ theta ... theta upsilon /sub i/ (i=0, 1, ..., n-1) in parallel in interconnection networks such as the omega network and the hypercube, where theta is an associative binary operator. Each algorithm can be embedded in the switches and interconnections of the network, and can be executed in O((log/sub 2/ r+1) log/sub r/ n) time steps provided that the network connecting n processors is constructed by using an r*r switch, and that parallelism within as well as among individual switches is exploited. The objective of these algorithms is to attain a communication pattern that fits the topology of the network. One type of network can be made equivalent to, or can be embedded in, another type of network, so a family of algorithms can be derived from one basic algorithm. In the basic algorithm, every processor p/sub i/ upward multicasts upsilon /sub i/ to processors p/sub k/ (k=i+1, i+2, ..., n - 1). En route to p/sub i/, upsilon /sub j/ (j=0, 1, ..., i - 1) are combined in the switches to produce the (i - 1)th initial prefix x/sub i-1/ that is received by p/sub i/, which can then compute the ith initial prefix x/sub i/=x/sub i-1/ theta upsilon /sub i/.
展开▼
机译：本文提出了一系列算法，用于从（upsilon / sub 0 /，upsilon / sub 1 /，...，upsilon / sub n-1 /）生成所有初始前缀x / sub i / = upsilon / sub 0 / theta upsilon / sub 1 / theta ... theta upsilon / sub i /（i = 0，1，...，n-1）在诸如omega网络和超立方体的互连网络中并行运行，其中theta是一个关联二进制运算符。每种算法都可以嵌入到网络的交换机和互连中，并且可以在O（（log / sub 2 / r + 1）log / sub r / n）个时间步中执行，只要连接n个处理器的网络由使用r * r开关，并利用了各个开关内部以及各个开关之间的并行性。这些算法的目的是获得适合网络拓扑的通信模式。一种类型的网络可以与另一种类型的网络等效或可以嵌入其中，因此可以从一种基本算法中得出一系列算法。在基本算法中，每个处理器p / sub i /向上组播upsilon / sub i /到处理器p / sub k /（k = i + 1，i + 2，...，n-1）。到p / sub i /的途中，upsilon / sub j /（j = 0，1，...，i-1）在交换机中组合以产生第（i-1）个初始前缀x / sub i- p / sub i /接收的1 /，然后可以计算第i个初始前缀x / sub i / = x / sub i-1 / theta upsilon / sub i /。
展开▼
