amehta@rdrc.rpi.edu (Alok Mehta) (10/24/89)
Hi, Can someone help me? I am looking at ways to automatically detect Parallelism and to schedule processors. It seems that most work in automatic parallelism attempts to find and split "FOR" loops. There are often restrictions. For example the code inside the "FOR" loop may not call other procedures. The characteristics of my problem are as follows: 1. PURELY FUNCTIONAL: Portions of the program are purely functional, ie, there are no side effects. For my problem, these portions are easily detected. 2. RECURSIVE: The code can be recursive. This leads me to believe that a simple FORK-JOIN technique is not sufficient. I must be able to detect when parallelism is desirable, and when it would cause too much overhead. At some level of granularity, it becomes less expensive to execute the code sequentially. This also leads me to believe that the parallelism detection should be performed dynamically (at Run Time), although some optimization can be done at compile time. 3. INTERPRETIVE: I have an interpreter for the language; ------------------------------------------- In these respects, the language is very similar to LISP, and Research Papers,etc for Parallel LISP would be very helpful. A typical application is for the traversing of an unbalanced tree. The tree is recursive, and it is not immediately obvious at which points the program should parallelize. ------------------------------------------- Other characteristics are: 1. It is a Database system. A copy of the database is assumed to be available to each processor. During the execution of purely functional procedures, we know that the database will not be modified. Database queries, are assumed to be done in Main Memory. The result of queries can be large, but will still fit into Main Memory. I am concerned about sharing results of queries among processors; In a SHARED MEMORY ARCHITECTURE, how can we organize the memory to minimize contention, while allowing processors to be able to access results computed by other processors? In a MESSAGE PASSING ENVIRONMENT, if several processors cooperate to solve a query, how can we merge the results efficiently? --------------------------------------------- I will compile a list of references (for my own research interests), and will send a copy to anyone who is interested. Please send responses to: mehtaa@cs.rpi.edu Thanks, Alok Mehta