PC market is filled with multiprocessor solutions today. That’s why modern software is required to use maximum hardware capabilities. Most sequential programs should be translated to their parallel equivalent in order to improve performance. The refactoring of software requires huge amount of work and funds, however nothing conceptually new is created. Rebuilt program will copy its predecessor features, thus not improving functional capabilities. Besides, new software is written much faster than tested and even when tested successfully, that doesn’t guarantee 100 percent protection from errors. Errors in software are common reasons to bad public opinion, thus bad sales. It’s common in game development, because game market is very active, so products should be created very fast. That makes a haste in development times, resulting in bad software quality. It’s no secret that some games contained critical errors by the time they shipped to consumers. Experienced developers prefer to use well-known and stable software, not to write from scratch. Stable software nowadays has its own long history of testing and fixing bugs. Most modern companies cannot afford this much time. That’s why most companies consider refactoring as unprofitable. It appears that most old software is written really good, so improvement of it should be very hard. Another problem is evading of errors. It’s natural for people to make mistakes. Mistakes give useful experience, which can be used to avoid such mistakes in future. People ought to think that machine does no errors, or much less than human, however machines are built by humans. Refactoring is very error-sensitive, so it’s better to perform it by machine in order to make no errors. General refactoring requires much intellect, much more than today’s software has. However, many refactoring works can be done by simply changing slow instructions to faster ones. Integer sum can be done faster by using MMè or SSE instructions. The path of program’s executions remains the same, however becomes much faster.
Today’s solutions of refactoring problems are partially automated. Special optimizing compilers are used, most designed to fit particular architecture. Some of those are optimizing Intel compilers, which perform much better on Intel processors. These solutions are ideal for fully designed program, where all code is static.
Improvement of program execution on virtual machines can be done much simpler by modifying only the virtual machine. This can be done by decreasing internal delays in virtual machine, such as parallel trash collection etc. These virtual machines do not make program parallel because they increase speed by decreasing internal delays. The main advantage of such solutions is immediate improvement of performance, without prior processing program source. Besides, these solutions speed up dynamically formed programs. Dynamic program creation is one of the core features for interpreted languages.
One of such languages is Lisp. Lisp is a functional language, with the same representation of code and data. The Lisp virtual machine is quite easy to implement. Lisp is the second high level programming language, initially designed for list processing. This feature oriented language for natural language constructs and artificial intelligence. Recursion and lambda-expressions made it popular to math researching. Prolog could be easily implemented in Lisp. The idea of recursive parallelism is as old as the Lisp itself, since it’s naturally designed for recursion.
The object of research is a Lisp translator model, which allows parallel program execution and performance improvement.
Parallel task execution in Lisp implementation is quite old. Many Lisp translators allow spawning new processes and threads in order to execute sub-tasks. First solutions were ported OS functions to work with processes and other system objects. The Common Lisp standard defined the system function call. However such solution was OS-dependant. Other solutions involved additional Lisp language constructs in order to define parallel execution. Those constructs were called “transparent” since they could be easily removed without altering program execution. One of such constructs is the “future”. “Future” became a standard of Lisp delayed tasks.
Kyoto Common Lisp (Kyoto university) – 1985,AOS/VS for ECLISPSE MV, Unix 4.2 bsd – Sun Workstation (based on Motorola 6800 processor). Parallel execution is written explicitly by using OS calls. This Common Lisp implementation was the most famous and powerful at that time, many implemented features were then added to standard. It included a C programming interface and a ported OS system functions, equivalent to C.
Multilisp 1985. First implementation of “future”. This construct provided an effective and elegant solution for parallel execution. The body of the “future” is evaluated concurrently with main task, and the on the place for result was a placeholder. After “future” evaluates, the placeholder is filled with results. Other tasks could use a placeholder to perform non-strict functions such as “cdr” or “cons”. As the result was needed – the task was suspended till placeholder was filled. In 1991 the “future” construct became a part of standard.
Qlisp (Lucid Inc) – 1989 (shared memory multiprocessor system). This implementation used additional language constructs, based on a set of low-level operations, such as “wait” and “throw”. The virtual machine spawned tasks intelligent, so that no more than number of processors can be spawned. The limitation of active tasks number was an efficient way to improve performance, since spawning more tasks than free processors, would lead to useless overhead.
Multilisp (Montreal university) – 1993. A new “future” implementation on MPI was created. In their work they compared two common “future” implementations, known as LTC(Lazy task creation) and ETC (Eager task creation). Their implementation of LTC allowed optimizing task management, thus making MPI implementation even more efficient than a shared-memory one.
TS/SCHEME (NEC) - 1994,STING, Silicon Graphics MIPS R4000 (distributed system for object-oriented Lisp). This distributed implementation used special language constructs for defining parallel execution.
BandaLisp (Singapore university) – 1994, SunOS 5.3 SunSparc Server 1000 (shared memory multiprocessor). This Scheme implementation featured special sequential memory usage with optimized compilation to machine code. As a result they achieved speeds, comparable to parallel C compiled programs. Despite common opinion that Lisp is much slower than C or other compiled languages, they proved Lisp could be as efficient as parallel C.
Beginning from 1995, Lisp interest fall down, that’s why there is so little literature from that period. From 2000 to 2007 there were no fundamentally new methods for expression of parallelism. There were some Open Source Lisp implementations on different platforms, however most of them were not ported to other platforms.
Main advantages of those implementations are their high efficiency, a powerful library base and support for object-oriented technologies.
However, all implementations require using special language structures to explicitly express parallelism. This feature makes these implementations unable to parallel execution of sequential programs without prior programmer processing.
In practice, most pure Lisp programs can be easily executed concurrently, since pure functions don’t use external variables. However, in order to allow writing sequential programs, some special constructs were introduced to Lisp. Most of that constructs encourage using global variables, so automatic concurrent execution should consider these cases too. Lisp syntax is rather simple and allows user to construct ill-formed programs, dynamically formed programs and even more exotic ones. Lisp allows overriding standard language functions and direct manipulation of atom associations. From this point of view Lisp is rather anarchic language, no language with type-checking can allow such programs. This feature cannot be considered as rather useful, since such programs are hard to understand and maintain. Some people think that strict program text is better, so such features must be disabled. Others are tend to think that it adds new ways of writing a program, makes it able to write unique programs. In this work author thinks that it’s a matter of taste whether to use such constructs or not, since Lisp allows it.
In this work all methods are good, so a conveyor can be organized in order to speed-up program processing. A parallel garbage collection should also be done. So a parallel virtual machine will be designed to decrease delays between useful computations and allowing parallel execution of sequential programs.
As a primary goal of research is a creation of parallel Lisp translator, which doesn’t require any additional constructs to express parallelism at all. In order to implement this, an analyzer of program execution is meant to include, featuring writing protocol of each task’s execution. A fallback mechanism will be inserted in order to save and restore the state of program while being executed. In order to control correct program execution, a fallback mechanism will be connected with self-diagnosis. The whole program text check is not an optimal solution, since only a part of it will be executed and the program can be formed at runtime. So, all performance improvement will be achieved at runtime. Portability of this translator will be achieved by using MPI.
The parallel translator can be used to parallel execution of dynamically formed programs and as a tool for sequential programs analysis.
At the time of writing the work is still in development, results should be ready in December 2007.