// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // package ComputerArchitecture.SystolicArrays.TransitiveClosure.KuLL87a; macro N = 3; // ---------------------------------------------------------------- // The disadvantage of the algorithm in LocDepWarshall.qrz is that the flows of // the propagating variables are done for most k's in two directions. // The following reindexed version removes this by diagonally shifting // the matrix t[][][k] in each step. Of course, the rotations can // also be performed on the original algorithm, which yields the // variant RotWarshall below (just for fun). RotLocDepWarshall // is more interesting, since now the flows of c and r are // unidirectional. // ---------------------------------------------------------------- module RotWarshall([N][N]bool ?a, [N][N][N]bool t, event !OnlyReflexive) { for(i=0..(N-1)) for(j=0..(N-1)) t[abs ((-1+i)%N)][abs ((-1+j)%N)][0] = a[i][j] | a[i][0] & a[0][j]; pause; for(k=1..(N-1)) { for(i=0..(N-1)) for(j=0..(N-1)) t[abs ((-1+i)%N)][abs ((-1+j)%N)][k] = t[i][j][k-1] | t[i][0][k-1] & t[0][j][k-1]; pause; } }