Innovative Computation Laboratory
The Innovative Computation Laboratory (ICL) has as its focus research and development of innovative computer systems and applications that are not constrained by commonplace hardware and software.
To download a software tool that solves discrete optimization problems using dynamic programming, click here. This tool models dynamic programming problems by Petri nets represented in a tabular spreadsheet form.
This project focuses in general on new applications of dynamic programming and other methods of discrete mathematics and operations research to the solution of discrete optimization problems that arise in computer science (especially as related to systems programming and software engineering) and in particular on ways in which dynamic programming algorithms can be more efficiently executed, whether by development of innovative algorithms, software, or hardware. Specific subprojects include the use of Petri models, called Bellman nets, in the design of dynamic programming software, and the use of functional memory and of tabular programming to solve dynamic programming problems.
This project further develops an innovative Petri net processing and simulation system, PNTBLSIM, that is based upon a tabular internal data representation for Petri nets. A primary advantage of the tabular data structure adopted is that it enables the implementation of a very simple Petri net simulator, one which does not require a graphical user interface and is still general enough to handle high-level Petri nets (including colored tokens, as for Bellman nets, and timed transitions). The possibility of implementing this simulator in hardware using a special-purpose processor (perhaps using functional memory) is being investigated. More complex systems that require a graphical user interface are also being planned. Related tasks include the design of new Petri net processing and simulation algorithms that exploit the tabular data structure representation for Petri nets, such as the SPNACG system that automatically generate GPSS or Simscript simulation code from the tables, and the application of such systems to a variety of software engineering problems. We are also exploring ways to incorporate rule-based expert system concepts as a part of this effort. The facility to simulate continuous as well as discrete systems remains a design objective. Of related interest, it should be noted that a Petri net simulator can be used to obtain the numerical solution of dynamic programming problems modeled as Bellman nets.
This project investigates the design and applications of computer systems based upon "functional memory," i.e., RAM with an attached field programmable gate array (FPGA) based coprocessor which can be dynamically reprogrammed to process in parallel the calculations of user computer programs in combinational logic. A functional memory computer should contribute to our work on a number of other projects, such as those related to Petri net simulation or to the solution of dynamic programming problems, but we expect it to also have independent value. Use of functional memory for the design of flexible multi-purpose coprocessing boards or custom computing machines has been our present focus. One potentially valuable application area of current interest is that of digital image processing.
This project explores various aspects of the use of tabular or table-based program structures (especially decision tables amd spreadsheets) as the basis of nonprocedural or less procedural programming. Subprojects include: (a) the design and analysis of table-based algorithms, both for general- purpose computation and for specialized applications such as expert systems and Petri nets and dynamic programming, for which implementations using tabular data structures appear to have certain advantages; (b) the design of special-purpose non-vonNeumann hardware, specifically, a microprogrammable processor using field programmable gate array chips for the execution of programs expressed in a tabular data structure, initially implemented, say, as a PC-compatible coprocessor; and (c) the development of software systems that support table-based programming on both conventional and special-purpose hardware.
For more information and/or feedback, please contact:
or write to:
Professor A. Lew
Innovative Computation Laboratory
Department of Information and Computer Sciences
University of Hawaii at Manoa
Honolulu, Hawaii 96822 (USA)
Interested faculty and students at the University of Hawaii, and outside parties as well, are invited to participate in the projects of the ICL. We would welcome your comments and your collaboration.
UH ICS Dept Home Page