// ************************************************************************** // // // // 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 finds for each node in a forest of trees its root. The// // forest of trees is encoded by an array that assigns node i its predecssor // // root pre[i]. The algorithm runs with O(log(N)) steps with work O(N*log(N)).// // ************************************************************************** // macro N=16; module FindRoots([N]nat ?pre,root,event !rdy) { // ------------------------------------------------------------------------- // first copy the predecessors to the root array // ------------------------------------------------------------------------- for(i=0..N-1) root[i] = pre[i]; // ------------------------------------------------------------------------- // pointer jumping: copy the root of the root log(N) times // ------------------------------------------------------------------------- for(l=1..log(N)) { for(i=0..N-1) next(root[i]) = root[root[i]]; pause; } emit(rdy); } drivenby t0 { // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 pre = [0,0,1,1,0,4,7,8,8,8, 9, 9, 3, 3, 6, 6]; await(rdy); } drivenby t1 { // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 pre = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15]; await(rdy); }