First, let us explain what the Towers of Hanoi is about. Given a stack of disks arranged from largest on the bottom to smallest on top placed on a rod, together with two empty rods, the towers of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks. It is a puzzle invented by E. Lucas in 1883. For nice illustrations of the Towers of Hanoi, we refer to http://mathworld.wolfram.com/TowerofHanoi.
A common approach is to implement the Towers of Hanoi as a simple recursive function. This function is, for instance, specified in the functional programmming language Lisp as follows.
(defun f (m) (+ (* 2 m) 1) (defun moves (n) (if (= n 0) 0 (f (moves (- n 1))))) (defun hanoi (n src dst aux) (if (= n 0) () (append (hanoi (- n 1) src aux dst) (list src dst) (hanoi (- n 1) aux dst src)))) (print (hanoi 10 'a 'c 'b))Intuitively, the above functional program implements a simple strategy to solve the Towers of Hanoi puzzle. That is, to move all disks from a to c using b as auxiliary peg do the following:
People that are less familiar with Lisp, but have some knowledge of the C programming language will find the following program easier to read. The C program first reserves a buffer that is large enough to hold the complete solution and then call the hanoi function.
#include <stdio.h> #define N 10 typedef struct { char src, dst; } move_t; void f(size_t m, size_t *result) { m <<= 1; *result = ++m; } void moves(size_t n, size_t *result) { if (n--) { moves(n,result); f(result,&result); } else { *result = 0; } } void hanoi(size_t n, char src, char dst, char aux, move_t *result) { size_t size; if (n--) { moves(n, &size); hanoi(n, src, aux, dst, result); result[size].src = src; result[size].dst = dst; hanoi(n, aux, dst, src, result + size + 1); } } int main() { size_t i, size; moves(N,&size); move_t buffer[size]; hanoi(N,'a','c','b',buffer); printf("("); for (i=0; i<size; ++i) { printf("(%c %c) ", buffer[i].src, buffer[i].dst); } printf(")\n"); return 0; }A standard C compiler translates the above program into so-called assembler instructions which are executed sequentially. This means that the exact order in which all instructions will be executed are known in advance. For many applications, however, it is often sufficient to specify the execution order only partially. Therefore, an Abbey compiler would not set up a fixed execution order. Instead, it creates a partial order of computational tasks where each task is identified by a function calls. Thereby, the different types of tasks are identified by function pointers in C. In the above program, for example, three types of functions are implemented; these functions are referred to by the (function) pointers: main, hanoi, moves and f. When the hanoi program is executed, the function main is called exactly once, which means that exactly one computational task of type main is assiociated with each run of the program. The hanoi function is recursively called many times; it generates many computational tasks which, in principle, can be executed concurrently.
It is up to the concurrency strategy how tasks will be executed concurrently as long as the partial order set up by the Abbey compiler will be respected. Currently, we don't use a ``real'' Abbey compiler yet, but we provide a set of easy-to-use C macros. The three most important macros are the following:
To understand the translation, lets first how have a look at Abbey-interpretable code of the very simple C function f which computes the function .
size_t tsk_f( aby_monk_t *monk, size_t argc, aby_var_t av_input, aby_var_t av_output ) { size_t m; ABY_VERIFY(argc,2); ABY_GET(av_input,m); m <<= 1; ++m; ABY_PUT(av_output,m); return argc; }Note that the original function f has two arguments. The input data for f is passed by value in the first argument, and the second argument is a pointer to the location where the result must be written. The Abbey cannot handle f if it is written in this way, because all arguments must be passed using so-called Abbey variables. Therefore, the above Abbey implementation of f, named tsk_f, takes two arguments of type aby_var_t. The first two arguments of every computational task have a predefined purpose which is as follows:
The first argument to f contains the input, and therefore, the first Abbey variable of tsk_f is a so-called input variable. To reflect this, the variable is called av_input. The second variable is a so-called output variable and is called av_output.
Before the data in an Abbey variable can we used it must first be copied into the memory using the ABY_GET macro. In tsk_f, the value of the Abbey variable av_input is read into the variable m. The result of a computational task in written into one or more output variables using ABY_PUT. Again in tsk_f, the result of computing is stored into the output variable av_output.
A slightly more complex task it the recursive function moves which is written as follows using the Abbey macros.
size_t tsk_moves( aby_monk_t *monk, size_t argc, aby_var_t av_n, aby_var_t av_result, aby_var_t av_aux ) { size_t n; ABY_VERIFY(argc,3); ABY_GET(av_n,n); if (n--) { ABY_PUT(av_n,n); ABY_CALL(monk,NULL,0,tsk_moves,2,av_n,av_aux); ABY_CALL(monk,NULL,0,tsk_f,2,av_aux,av_result); } else { n = 0; ABY_PUT(av_result,n); } return argc; }Note that the macro ABY_CALL is used in the implementation of tsk_moves. The macro ABY_CALL takes a variable number of arguments2. The arguments are as follows:
A static Abbey call sets up an asynchronous call to the function specified as the fourth argument and passes the amount of Abbey variables to the computational task that is specified by the fifth argument. The Abbey variables themselves are provided in argument six and higher. In the implementation of tsk_moves shown above two Abbey calls are set up:
It is interesting to note that the recursive call in tsk_moves passes only two arguments while actually three arguments are expected. The system will create the third variable on-the-fly and passed it to the newly invoked computational task. In this way, a new variable that functions as a kind of auxiliary variable is created for each recursive call. These auxiliary variables are needed for concurrency reasons. To understand this, suppose that we would have written the two asynchronous calls in the following way without using the auxiliary variable:
ABY_CALL(NULL,0,tsk_moves,2,av_n,av_result); ABY_CALL(NULL,0,tsk_f,2,av_result,av_result);The above code is incorrect, because it will result in a deadlock most of the time. The reason for the deadlock is that typically multiple calls to tsk_f will be created that run concurrently. These calls then all want to read from the same Abbey variable which is impossible: only one read can succeed and the others will block. The use of the auxiliary variable prevents this however. To prevent deadlock in general, we have to make sure that every input variable is used exactly once. In more complex tasks, this means that input variables must be ``split'' (this is called teeing) into multiple different variables.
This happens, for example, in the implementation of hanoi below. To split off variables dynamic Abbey calls are needed. In a dynamic Abbey call arguments 2 and 3 are used to append variables to the argument list which are created on-the-fly. The idea is as follows:
To understand the difference between static and dynamic Abbey calls consider the translation of hanoi into Abbey-interpretable code.
size_t tsk_hanoi( aby_monk_t *monk, size_t argc, aby_var_t av_n, aby_var_t av_src, aby_var_t av_dst, aby_var_t av_aux, aby_var_t av_amount, ... ) { char src, dst; size_t n, size; move_t move; aby_var_t *av_argv, av_size; struct { aby_var_t a; aby_var_t b; aby_var_t c; } t_src, t_dst, t_n; struct { aby_var_t a; aby_var_t c; } t_aux, t_amount; av_argv = &av_amount; av_argv++; ABY_CALL(monk,&t_n.a,3,tsk_alloc,1,av_amount); ABY_GET(av_amount,n); ABY_CALL(monk,&t_amount.a,2,tsk_alloc,1,av_amount); ABY_GET(av_amount,n); ABY_GET(av_n,n); if (n--) { ABY_PUT(t_n.b,n); ABY_CALL(monk,&av_size,1,tsk_moves,1,t_n.b); ABY_GET(av_size,size); struct size_st { aby_var_t av_argv[size]; }; ABY_CALL(monk,&t_src.a,3,tsk_tee,1,av_src); ABY_CALL(monk,&t_dst.a,3,tsk_tee,1,av_dst); ABY_CALL(monk,&t_aux.a,2,tsk_tee,1,av_aux); ABY_PUT(t_n.a,n); ABY_CALL(monk,NULL,0, tsk_hanoi,5+size, t_n.a,t_src.a,t_aux.a,t_dst.a,t_amount.a, *((struct size_st *) av_argv) ); ABY_GET(t_src.b,src); ABY_GET(t_dst.b,dst); move.src = src; move.dst = dst; ABY_PUT(av_argv[size],move); ABY_PUT(t_n.c,n); ABY_CALL(monk,NULL,0, tsk_hanoi,5+size, t_n.c,t_aux.c,t_dst.c,t_src.c,t_amount.c, *((struct size_st *) (av_argv + size + 1)) ); } return argc; }The above implementation of tsk_hanoi contains several dynamic calls to two tasks that are so-called Abbey buildins, i.e., implementations of computational tasks that are provided in the Abbey library. These two buildin tasks are: tsk_alloc and tsk_tee.
The task tsk_alloc is used to create new variables explicitly. That is, the following call initializes a vector of n variables pointed to by av_argv.
ABY_CALL(av_argv,n,tsk_alloc,1,av_amount);The value of n is assigned to av_amount. This means that after ABY_GET(av_amount,n) returns that variables in the array av_argv can be assumed to be initialized and ready for use.
The task tsk_tee is used to split a variable. The first argument of this computational task is an input variable and the rest are output variables. The computational tasks reads from the input variable and writes it to all output variables.
The implementation tsk_hanoi uses the two buildin function in the following way. First, it creates new variables to contain three copies of the value to be passed to subtasks later on. Next, it creates two variables for the Abbey variable av_amount, because for each recursive call this variable is required to be newly created. Finally, the input variable av_n is read and decremented, and the recursive calls are setup using sufficient calls to tsk_tee in order to avoid deadlock.
The translation of the function main is similar and looks as follows.
size_t tsk_main( aby_monk_t *monk, size_t argc, aby_var_t av_src, aby_var_t av_dst, aby_var_t av_aux, aby_var_t av_size, aby_var_t av_amount ) { char x; size_t i, size; move_t move; struct { aby_var_t a; aby_var_t b; } t_n; ABY_VERIFY(argc,5); ABY_CALL(monk,&t_n.a,2,tsk_alloc,1,av_size); ABY_GET(av_size,i); i = N; ABY_PUT(t_n.a,i); ABY_PUT(t_n.b,i); ABY_CALL(monk,NULL,0,tsk_moves,2,t_n.a,av_size); ABY_GET(av_size,size); struct { aby_var_t v[size]; } t_result; ABY_CALL(monk,(aby_var_t *) &t_result,size,tsk_alloc,1,av_size); ABY_GET(av_size,i); x = 'a'; ABY_PUT(av_src,x); x = 'c'; ABY_PUT(av_dst,x); x = 'b'; ABY_PUT(av_aux,x); ABY_CALL(monk,NULL,0, tsk_hanoi,5+size, t_n.b, av_src, av_dst, av_aux, av_amount, t_result ); printf("("); fflush(stdout); for (i=0; i<size; ++i) { ABY_GET(t_result.v[i],move); printf("(%c %c) ", move.src, move.dst); fflush(stdout); } printf(")\n"); return argc; }First, we copy the value N into two variables The first variable is used to determine the size of the solution. The second variable is used for calling tsk_hanoi. Next, to setup the call to tsk_hanoi, we create just as many variables as the size of the solution and pass them to the computational task. Finally, the output variables are read and the solution is printed.
Knoppix User 2006-03-15