// ************************************************************************** // // // // 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 // // // // ************************************************************************** // // The following module computes the predecessors and successors of a set of // // nodes phi of a graph. The graph is given by a boolean matrix, and the sets // // are given as boolean vectors. Using O(N^2) processors, both sets can be // // computed in parallel in time O(1) using a CRCW PRAM. // // ************************************************************************** // macro N = 9; module PreSucStates([N][N]bool ?a,[N]bool ?phi,pre,suc) { // check all edges and notify the result by concurrent writes for(i=0..N-1) for(j=0..N-1) { if(a[i][j] & phi[j]) pre[i] = true; if(a[i][j] & phi[i]) suc[j] = true; } } drivenby g1 { // the assignments below construct the following graph: // // 3 // / \ // v v // 0 -> 1 <-> 2-> 4 <-> 5 <-> 6 // | | // v v // 7<| 8 // |_| // a[0][1] = true; a[1][2] = true; a[2][1] = true; a[2][4] = true; a[2][7] = true; a[3][2] = true; a[3][4] = true; a[4][5] = true; a[5][4] = true; a[5][6] = true; a[5][8] = true; a[6][5] = true; a[7][7] = true; phi[2] = true; phi[4] = true; phi[5] = true; for(i=0..N-1) { assert(pre[i] == (1<=i & i<=6)); assert(suc[i] == (i==1 | 4<=i)); } }