::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-10 The FAD Project C. W. Liew L. Steinberg Design is much easier when the design problem can be decomposed into small pieces that can be solved independently and then easily combined to form a solution. However, when the design goals include limiting overall usage of some resources, e.g. for a digital circuit limits on computation time or silicon area, interactions often arise which make it difficult to determine what effect some decision about a small piece of an artifact will have on the overall quality of the solution. Thus decomposition becomes impossible and, if the problem is too large to handle by exhaustive search, finding a good solution is very hard. We have focussed our attention primarily on the task of High-Level Synthesis (HLS) of VLSI digital circuits - the process of converting a computation specified in a language much like a programming language into a register-transfer level description of a circuit to carry out this computation. Real problems in this domain involve not just producing functionally correct circuits, but also circuits that use limited amounts of time and silicon area, and perhaps also limited power. They are often very large and complex problems, and require many decisions, and many kinds of decisions, to be made before a solution is generated. The space of possible solutions is therefore very large and it is not feasible to examine all possible solutions. Thus, this domain is a good example of problems where global interactions due to multiple resource constraints combine with a large search space to make design hard. The standard approach taken by current programs which do HLS is to none the less treat groups of decisions as if they were independent, and to use a heuristic function to estimate how good a proposed partial solution is. Unfortunately, these heuristics are not good enough (and as we will discuss below {\em cannot} be good enough) to produce designs competitive with those of human designers. This paper describes a new approach we have developed for solving such problems, which we call {\em Feedback Aided Design} (FAD). Since we can only really tell how good a design is when it is complete, our approach essentially does a {\em search in the space of complete designs.} However, each step we make in this space is not made by directly perturbing the previous design. Rather, we design a complete circuit using standard methods, analyze it to propose a few key decisions which should have been made differently than they were, and rerun the standard design methods with the added constraints on how these specific decisions are to be made. Thus, we wrap the standard methods in an outer loop which runs them, analyzes the resulting circuit, and produces constraints which are the used as feedback to guide the next iteration of design. Our approach does not require additional software to ensure the correctness of the final solution, a requirement that would be needed if our search entailed direct modification of the design. Although our approach depends strongly on domain knowledge to do the analysis, we believe our framework gives important guidance as to what domain knowledge is needed and how a system can be structured to use it. We believe this framework should transfer to a number of important domains besides High-Level Synthesis. The approach is being implemented in the FAD System. This work is part of the CAP (Computer Aided Productivity) Project, a long term research effort in the Laboratory for Computer Science Research at Rutgers University aimed at modelling the design process and developing knowledge-based design systems for a spectrum of design domains. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-11 Intelligent Model Selection for Hillclimbing Search in Computer-Aided Design Thomas Ellman John Keane Mark Schwabacher Department of Computer Science Hill Center for Mathematical Sciences Rutgers University New Brunswick, NJ 08903 {ellman,keane,schwabac}@cs.rutgers.edu CAP-TR-11 Models of physical systems can differ according to computational cost, accuracy and precision, among other things. Depending on the problem solving task at hand, different models will be appropriate. Several investigators have recently developed methods of automatically selecting among multiple models of physical systems. Our research is novel in that we are developing model selection techniques specifically suited to computer-aided design. Our approach is based on the idea that artifact performance models for computer-aided design should be chosen in light of the design decisions they are required to support. We have developed a technique called ``Gradient Magnitude Model Selection'' (GMMS), which embodies this principle. GMMS operates in the context of a hillclimbing search process. It selects the simplest model that meets the needs of the hillclimbing algorithm in which it operates. We are using the domain of sailing yacht design as a testbed for this research. We have implemented GMMS and used it in hillclimbing search to decide between a computationally expensive potential-flow program and an algebraic approximation to analyze the performance of sailing yachts. Experimental tests show that GMMS makes the design process faster than it would be if the most expensive model were used for all design evaluations. GMMS achieves this performance improvement with little or no sacrifice in the quality of the resulting design. (Appears in the Proceedings of the Eleventh National Conference on Artificial Intelligence, Washington, D.C., July, 1993) ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-13 Constrained REDO: An Alternative to REPLAY C. W. Liew L. I. Steinberg Department of Computer Science Rutgers University New Brunswick NJ 08903 Email: liew@cs.rutgers.edu, lou@cs.rutgers.edu Phone: (908)932-5229 Design optimization problems and VLSI microprocessor design in particular, are complex problems with some characteristics that make them very different from the problems that AI researchers have traditionally studied. Case based reasoning is a valuable tool that can be used to make these problems tractable. Traditional case based methods with their use of REPLAY based techniques are unsuitable because they rely on the use of design records and decision trees. CONSTRAINED-REDO is a new technique that does not use design records but instead relies on an analysis of the solution and the propagation of information through constraints. These constraints are not on the design decisions but only refer to the mapping between the problem specification and the solution. The technique has been tested in a real-world domain, that of VLSI microprocessor design. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-14 Abstraction and Decomposition in Hillclimbing Design Optimization Thomas Ellman Mark Schwabacher Department of Computer Science Hill Center for Mathematical Sciences Rutgers University New Brunswick, New Jersey 08903 (908) 932 - 4184 {ellman,schwabac}@cs.rutgers.edu The performance of hillclimbing design optimization can be improved by abstraction and decomposition of the design space. Methods for automatically finding and exploiting such abstractions and decompositions are presented in this paper. A technique called ``Operator Importance Analysis'' finds useful abstractions. It does so by determining which of a given set of operators are the most important for a given class of design problems. Hillclimbing search runs faster when performed using this this smaller set of operators. A technique called ``Operator Interaction Analysis'' finds useful decompositions. It does so by measuring the pairwise interaction between operators. It uses such measurements to form an ordered partition of the operator set. This partition can then be used in a ``hierarchic'' hillclimbing algorithm which runs faster than ordinary hillclimbing with an unstructured operator set. We have implemented both techniques and tested them in the domain of racing yacht hull design. Our experimental results show that these two methods can produce substantial speedups with little or no loss in quality of the resulting designs. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-15 TITLE: Approximation Operators in Distributed Modeling AUTHOR: Sui-ky Ringo Ling and Louis Steinberg Department of Computer Science Rutgers University New Brunswick, NJ 08904 ling@cs.rutgers.edu, lou@cs.rutgers.edu ABSTRACT: Computer programs which do any task which requires reasoning about physical systems need to use models of those systems with varying accuracy/complexity tradeoffs. This paper describes an approach to model generation in the domain of heat transfer which is capable of producing models that vary greatly along this dimension. This approach is based on the law of conservation of energy, which provides a set of choices for the models in terms of ``control volumes'' and heat flows. These choices are made by using rules of thumb, which can be seen as instances of two reduction operators, delta-iso and dominance. Various rough models are used to estimate the physical parameters on which these rules depend. That is, the rough models are evaluated in the process of building more accurate ones. The application of these operators is only valid for a specific set of physically meaningful quantities; thus we are really reasoning about physics, not equations. This method has been implemented in a running system, MSG. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-16 Modeling and Simulation for Automated Yacht Design Andrew Gelsey gelsey@cs.rutgers.edu Appeared: AAAI Fall Symposium, 1992 Computational simulation is an important tool for predicting the behavior of physical systems. Many powerful simulation programs exist today. However, using these programs to reliably analyze a physical situation requires considerable human effort and expertise to set up a simulation, determine whether the output makes sense, and repeatedly run the simulation with different inputs until a satisfactory result is achieved. Automating this process is not only of considerable practical importance but also raises significant AI research issues in the areas of spatial reasoning and modeling of physics and numerical methods. The application domain described in this paper is the design of racing yachts. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-17 Learning Prototype-Selection Rules for Case-Based Iterative Design Mark Schwabacher Haym Hirsh Thomas Ellman Department of Computer Science Rutgers University New Brunswick, NJ 08903 CAP-TR-17 The first step for most case-based design systems is to select an initial prototype from a database of previous designs. The retrieved prototype is then modified to tailor it to the given goals. For any particular design goal the selection of a starting point for the design process can have a dramatic effect both on the quality of the eventual design and on the overall design time. We present a technique for automatically constructing effective prototype-selection rules. Our technique applies a standard inductive-learning algorithm, C4.5, to a set of training data describing which particular prototype would have been the best choice for each goal encountered in a previous design session. We have tested our technique in the domain of racing-yacht-hull design, comparing our inductively learned selection rules to several competing prototype-selection methods. Our results show that the inductive prototype-selection method leads to better final designs when the design process is guided by a noisy evaluation function, and that the inductively learned rules will often be more efficient than competing methods. Appears in the Proceedings of the Tenth Conference on Artificial Intelligence for Applications, San Antonio, Texas, March, 1994 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-18 TITLE: MSG: A Computer System for Automated Modeling of Heat Transfer AUTHORS: Sui-ky Ringo Ling and Louis Steinberg Department of Computer Science Rutgers University New Brunswick, NJ 08903 Yogesh Jaluria Department of Mechanical and Aerospace Engineering Rutgers University New Brunswick, NJ 08903 ABSTRACT: The task of modeling, i.e. of creating a set of equations that can be used to predict the behavior of a physical object, is a key step in engineering analysis. This paper describes a computer system, MSG, for generating mathematical models to analyze physical systems involving heat transfer behavior. MSG is motivated by the need for modeling in an automated design process. The models are sets of equations which may include algebraic equations, ordinary differential equations and partial differential equations. MSG uses the strong domain theory to guide model construction in three sequential tasks: identify regions of interests on an object, determine relevant heat transfer and energy storage processes, and transform these processes into equations. The decisions in these tasks are guided by estimates of variation in temperature and material property, and the relative strengths of heat transfer processes. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-2 Combining Innovation and Perspiration Louis Steinberg Department of Computer Science Rutgers University New Brunswick, NJ 08903 USA lou@cs.rutgers.edu [paper for WORKSHOP ON ARTIFICIAL INTELLIGENCE IN DESIGN at IJCAI-91] For many design problems, the requirements and/or the available technology change quickly relative to the design cycle. As a result each new artifact designed involves some degree of innovation, and there is much that the designer must learn in the process of doing the design. The Computer Aided Productivity (CAP) Project at Rutgers has been carrying out a retrospective study of just such a task, the design of the sailboat, Stars \& Stripes 87, which won the 1987 America's Cup races. The work is still in progress, but already a number of interesting observations have been made: \begin{itemize} \item Innovation is spurred and guided by perceived opportunity. \item Innovation often involves borrowing an idea from another context rather than the creation of something totally new. \item In innovative design, much of the exploration is to gain information needed to set up the problem as an optimization/search problem. \item One of the key questions is which analysis method to use when. \item A useful guide to design task decomposition is to consider the different physical processes at work. \end{itemize} ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-21 Intelligent Automated Quality Control for Computational Simulation Andrew Gelsey gelsey@cs.rutgers.edu CAP-TR-21 August 1994 Computational simulation of physical systems generally requires human experts to set up a simulation, run it, evaluate the quality of the simulation output, and repeatedly invoke the simulator with modified input until a satisfactory output quality is achieved. This reliance on human experts makes use of simulators by other programs difficult and unreliable, though invocation of simulators by other programs is critical for important tasks such as automated engineering design optimization. I present a framework for constructing intelligent controllers for computational simulators which can automatically detect a wide variety of problems which lead to low-quality simulation output, using a set of evaluation methods based on knowledge of physics and numerical analysis stored in a data/knowledge base of models and simulations. I describe an experimental implementation of this framework in an intelligent automated controller for a widely used computational fluid dynamics simulator. Computer Science Department\\ Rutgers University\\ New Brunswick, NJ 08903 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-6 PROGRESS REPORT FOR YEAR 2 OF THE RESEARCH GRANT ON AI AND DESIGN: COMPUTER AIDED PRODUCTIVITY (CAP) AND PLAN FOR YEAR 3 Saul Amarel, PI Louis Steinberg, Co-PI Tom Ellman Andrew Gelsey Haym Hirsh Jerry Richter ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-7 The Rutgers CAP Project Design Associate Thomas Ellman John Keane Mark Schwabacher Department of Computer Science Rutgers University Hill Center for Mathematical Sciences New Brunswick, New Jersey 08903 {ellman,keane,schwabac}@cs.rutgers.edu CAP-TR-7 The Design Associate is intended to be an interactive environment that supports decision-making, performance evaluation, design-record management and knowledge acquisition tasks. The system is specifically intended to handle the design of complex, physical structures, such as ships and planes, among others. Two key difficulties characterize this class of design problems: (1) Design goals depend on global properties of an artifact. (2) Evaluation of the performance of an artifact is computationally expensive. The Design Associate provides a set of tools for attacking each of these problems: Global constraints are attacked by methods of automatically abstracting and decomposing search spaces. Computational costs of evaluation are attacked by methods of intelligently selecting evaluation models at varying levels of approximation. Future work will extend the Design Associate by building a Model Associate for automatically generating new performance evaluation models. This extension is intended to support innovative design by diminishing the time and monetary costs of developing new models needed to evaluate radically new designs. Research on the Design Associate is expected to contribute to the field of Computer-Aided Design by formalizing the generic task structure of complex, physical structure design. It is also expected to contribute to the field of Artificial Intelligence, by attacking problems such as search control, search space formulation, abstraction, decomposition, model selection and model formation. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-8 Artificial Intelligence Research Issues in Computational Simulation of Physical System Behavior Andrew Gelsey gelsey@cs.rutgers.edu March 1992 Computational simulation is an important tool for predicting the behavior of physical systems. Many powerful simulation programs exist today. However, using these programs to reliably analyze a physical situation requires considerable human effort and expertise to set up a simulation, determine whether the output makes sense, and repeatedly run the simulation with different inputs until a satisfactory result is achieved. Automating this process is not only of considerable practical importance but also raises significant AI research issues in the areas of spatial reasoning and deep models of expert reasoning about physics and numerical analysis. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: CAP-TR-9 Model Generation from Physical Principles: A Progress Report Ringo Ling and Louis Steinberg} Department of Computer Science Rutgers University New Brunswick, NJ 08904 ling@cs.rutgers.edu, lou@cs.rutgers.edu Abstract This paper describes a framework and a system for generating mathematical models (i.e. sets of equations) for analyzing physical systems. The models are derived from physical principles, and include not only models based on algebraic and ordinary differential equations (i.e. ``lumped'' models), but also those based on partial differential equations (i.e. ``distributed'' models). We are motivated by the need for analysis models to be used in designing artifacts, and focus on the domain of thermal manufacturing. Our framework involves three sequential subtasks: identify regions of interest on the artifact, determine and identify the relevant physical processes, transform the set of individual processes into equations and carry out mathematical simplification. We take the view that understanding the task of model generation is fundamental to our future research on approximate modeling in design. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TM-1 Title: Notes on the Technical Sessions of the First HPCD Workshop Author:M. Schwabacher and J. Keane Date: September, 1994 Abstract: This is the first annual workshop of the ARPA-sponsored project on "Hypercomputing and Design" (HPCD). The borad objective of HPCD is to build on top of advances in HPC and in other areas of computer and computational science [especially in AI and in Modeling/Simulation technology], and to develop a new generation of automation technology for solving complex problems of engineering design. The objective of the workshop is to review the status and directions of HPCD research. The workshop is expected to ring together all the project investigators and affiliates, the ARPA PM and other ARPA people close to the project, members of the HPCD Technical Advisory Committee, and selected "friends of the project" from academia, industry, and government - to review ongoing technical work in all areas of the project, to strengthen collaborations, and to discuss plans for future work. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TM-2 Notes on the second HPCD Workshop Mark Schwabacher and John Keane July 1995 The second HPCD Workshop was held at Rutgers University on July 20 and 21, 1995, which was approximately the midpoint of the second of four years of the project. The goals of the workshop were to review the project goals, to bring together the people related to the project, and to get a good "big-picture" overview of project progress. During the technical sessions of the workshop, investigators from each of the project's areas summarized the research that had been done in the previous year. This memo summarizes these talks. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TM-3 Title: Notes on the third HPCD Workshop Authors: Brian Davison and Khaled Rasheed Abstract: The third HPCD Workshop was held at Rutgers University on July 18 and 19, 1996, which was approximately the midpoint of the third year of the four year project. The workshop provided the opportunity to review the project goals, to bring together the people related to the project, and to get a good "big-picture" overview of project progress. During the technical sessions of the workshop, investigators from each of the project's areas outlined the research that had been done in the previous year. This memo briefly summarizes each talk and any ensuing discussion. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TM-4 Title: Notes on the fourth HPCD Workshop Authors: Brian D. Davison and Keith M. Miyake Abstract: The fourth HPCD Workshop was held at Rutgers University on July 17 and 18, 1997, which was approximately the midpoint of the fourth year of the four year project. The workshop provided the opportunity to review the project goals, to bring together the people related to the project, summarize the experiences, and identify spinoffs and outgrowths of the HPCD effort. During the technical sessions of the workshop, investigators from each of the project's areas summarized the research that had been done in the project, concentrating on the previous year. This memo briefly outlines each talk and any ensuing discussion. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-1 Efficient Algorithms and a Software Tool for Scheduling Parallel Computation. Apostolos Gerasoulis, Rutgers University Tao Yang, University of California at Santa Barbara\\ Abstract: To parallelize an application program for a distributed memory architecture, we can use a precedence task graph to represent the parallelism of this program, schedule tasks onto the given physical processors and then distribute program and data accordingly. In this chapter, we discuss program partitioning techniques for constructing task graphs and present several static scheduling algorithms that consider the overhead of inter-processor communication. Finally we give an overview of a software system PYRROS that uses scheduling algorithms to generate parallel code for distributed memory parallel machines. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-10 Title: A 2-D Compressible Navier-Stokes Algorithm Using an Adaptive Unstructured Grid Author: H.F. Lau and D. Knight Date: June, 1994 Abstract: The results of a two-dimensional, compressible, Navier-Stokes solver using an unstructured grid with adaptive remeshing are presented in this paper. Roe's flux-difference splitting method and Gauss's Theorem were used correspondingly to represent the inviscid and viscous terms of the Navier- Stokes equation. Temporal integration is performed with a modified Runge- Kutta method. Mesh adaptation is accomplished through five simple error indicators. They are the undivided difference of density, velocity and energy, and the Laplacian of velocity and temperature. After the adaptive process, a global remeshing of the domain was performed using an efficient mesh generator. Two problems were analyzed by the adaptive algorithm. The first was a supersonic flat plate boundary layer at a free stream Mach number M 00 = 2.0 and Reynolds number (based on the plate length) Re plate = 6.5 X 10 @+(4). The results were compared with the theoretical Blasius solution. The second case was viscous flow past a NACA 0012 airfoil at zero angle of attack. The numerical solutions was compared to computational results obtained by the Beam-Warming scheme. Good agreement was observed for both the boundary layer and airfoil computations. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-11 Title: Differences in Algorithmic Parallelism in Control Flow and Call Multigraphs Author: V. Sgro and B. Ryder Title: September, 1994 Abstract: Our parallel hybrid analysis methods facilitate the parallelization of the analysis phase of a software transformation system, by enabling deeper semantic analyses to be accomplished more efficiently than if performed sequentially. Our previous empirical studies profiled these hybrid techniques on the Reaching Definitions problem [LMR91, LR92a, LR92b]. Recently, we have applied our method to the InterproceduralMay_Alias Problem for Fortran programs in a prototype implementation. The interpretation of our results suggested further performance studies, comparing our region partition algorithms (both Bottom_Up and Forward partitioning [LRF94] on call multigraphs and control flow graphs. These comparisons yielded statistically significant differences in performance of our graph partitioning techniques applied to these two graph populations. This research is part of a larger effort to calculate the modification side effects problem (MOD) for Fortran programs using our parallel hybrid techniques. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-12 Title: Automated Modeling of Distributed and Lumped Phenomena in Heat Transfer (THESIS) Author: Sui-Ky Ringo Ling Date: October, 1994 Abstract: Modeling is an important first step in scientific computation and engineering analysis. It is a complex process of formulating approximate and yet accurate enough mathematical representations of physical phenomena in scientific computation and computational science. This thesis demonstrates that the modeling of complex heat transfer phenomena involving partial differential equations can be automated. This thesis presents a computa The approach has been implemented in a computer program, MSG. The input to MSG consists of geometric and material properties information about an object, a set of initial and boundary conditions and a query that a model is supposed to answer. The output is a mathematical model and a list of the assumptions that MSG makes about the model. The system has been tested in modeling heat transfer in solids of single or multiple components with models including algebraic, ordinary differential and partial differential equations. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-13 Feedback Directed Optimization Chun Wai Liew HPCD-TR-13, CAP-TR-23 Optimization is a very important part of the design process. There are few design problems where concerns for either cost, quality, design time, etc., are not important. A great deal of time and design effort is spent on determining how to generate a solution that is optimized for a particular set of criteria, e.g., cost or time. However, optimization remains an ill-understood part of the process in many design problems. This thesis describes an innovative approach towards finding good solutions, i.e., optimized solutions, by using information about interactions between components (local interactions) gleaned from earlier solutions. The approach is called Feedback Directed Optimization (FDO). FDO is an iterative design approach based on the assumption that information about local interactions between solution components are essential towards being able to converge on good solutions to resource optimization problems. The approach includes techniques for (1) credit-blame assignment to determine where local interactions occur that might have been overlooked by the problem solver (2) controlling the problem solver on subsequent iterations to generate better solutions. These techniques have been developed and tested on several problem solvers in multiple domains. In addition, we have analysed the approach and have developed a prescriptive framework whereby new and existing problem solvers can use our techniques. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-18 Title: Computing and Problems of Complex Mechanical System Design Author: Saul Amarel Date: February, 1995 Abstract: The primary sections of this report are: I. Focus, II. Driving Questions, VI. Agile Design XII. Summary of Critical Research Areas; Priorities; Suggested Approach XIII. Recommendation; they convey the main substance of the report, and they can be read in lieu of Executive Summary. The remaining sections provide additional technical detail and clarification. The Appendix describes in detail the three specific design scenarios that we have considered during our study. By examining these scenarios, we have identified/analyzed the primary technical gaps that exist between the present state of best design practice and the (much) improved state that we are envisioning in a decade. The References (Section XIV) include several ISAT reports, as well as other ARPA-sponsored reports, that describe previous studies in areas of computer- aided design and manufacturing, and in related areas of modeling and simulation. Much of the background and rationale for the present study can be found in these previous reports. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-19 Title: 4th Quarterly R&D Status Report Author: Saul Amarel Date: September, 1994 Abstract: This report covers the fourth quarter of the "Hypercomputing and Design" (HPCD) project. Activities initiated during the previous three periods of the project have gained additional momentum. Special efforts were made to strengthen collaborative links between research areas. The project is gaining more cohesiveness as research directions are becoming better defined in light of the overall project theme. The quarter began with the first annual HPCD Workshop. The objective of the workshop was to review the status and directions of HPCD research. The workshop brought together the project investigators and affiliates, ARPA people close to the project, members of the HPCD Technical Advisory Committee, and selected "friends of the project" from academia, industry and government. The participants reviewed ongoing technical work in all areas of the project and discussed plans for future work. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-2 Title: 1st Quarterly R&D Status Report Author: Saul Amarel Date: December, 1993 Abstract: The Hypercomputing and Design (HPCD) project started officially on October 13, 1993. This report covers the first three months of the project. Our proposal for HPCD was submitted to ARPA on May 15, 1992; and much of our planning for the project took place in late '91. Despite the two-year interval between planning and actual beginning of the project, we were able to create during this reporting period an initial momentum, which in terms of people participation and enthusiasm, establishment of collaborative links, and development of ideas and technical plans - is already moving the project in the direction that we envisioned in the proposal. Basically, much of the present period was devoted to "getting the project off the ground", i.e., to formulating updated technical plans, and to establishing updated guidelines for research collaborations. To provide some background and context for the technical progress during this first reporting period, we are also reporting on some closely related work, which was done by HPCD investigators in the months preceding the start of the project and which is based on ideas that are presented in the proposal and that are expected to provide starting points for work in the project. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-20 A Search Space Toolkit Andrew Gelsey Don Smith Mark Schwabacher Khaled Mohamed Rasheed Shehata Keith Miyake The Search Space Toolkit (SST) is a suite of tools for investigating the properties of the continuous search spaces which arise in designing complex engineering artifacts whose evaluation requires significant computation by a numerical simulator. SST has been developed as part of NDA, a computational environment for (semi-)automated design of jet engine exhaust nozzles for supersonic aircraft, which was developed in a collaboration between computer scientists at Rutgers University and design engineers at General Electric and Lockheed. Though the design spaces for this sort of engineering artifact are mainly continuous, they typically include features such as unevaluable points, multiple local optima, and large derivatives which cause difficulties for standard numerical optimization methods. The search spaces which SST explores also differ significantly from the discrete search spaces that typically arise in artificial intelligence research, and properly searching such spaces requires a synergistic combination of numerical methods and AI techniques and is a fundamental AI research area. By promoting the design space to be a first class entity, rather than a ``black box'' buried in the interface between an optimizer and a simulator, SST allows a more principled approach to automated design. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-21 A Computational Environment for Exhaust Nozzle Design Andrew Gelsey Don Smith The Nozzle Design Associate (NDA) is a computational environment for the design of jet engine exhaust nozzles for supersonic aircraft. NDA may be used either to design new aircraft or to design new nozzles that adapt existing aircraft so they may be reutilized for new missions. NDA was developed in a collaboration between computer scientists at Rutgers University and exhaust nozzle designers at General Electric Aircraft Engines and General Electric Corporate Research and Development. The NDA project has two principal goals: to provide a useful engineering tool for exhaust nozzle design, and to explore fundamental research issues that arise in the application of automated design optimization methods to realistic engineering problems. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-22 NPARC Simulation and Redesign of the NASA P2 Hypersonic Inlet Andrew Gelsey Doyle D. Knight Song Gao Mark Schwabacher The NPARC Reynolds-averaged Navier-Stokes code was used in a systematic redesign of the NASA P2 hypersonic inlet. The first phase of the work involved computational experiments to determine appropriate grid densities, etc. for using NPARC to achieve grid-converged simulations of the P2 inlet which adequately matched published experimental data. The second phase of the work involved formulating the redesign of the P2 inlet as a numerical optimization problem which was attacked using state-of-the-art numerical optimization software. The resulting P2 inlet design is significantly superior to the original design. In particular, the static pressure distortion at the throat was reduced by more than a factor of five. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-23 Intelligent Automated Grid Generation for Numerical Simulations Ke-Thia Yao Andrew Gelsey Numerical simulation of partial differential equations (PDEs) plays a crucial role in predicting the behavior of physical systems and in modern engineering design. However, in order to produce reliable results with a PDE simulator, a human expert must typically expend considerable time and effort in setting up the simulation. Most of this effort is spent in generating the grid, the discretization of the spatial domain which the PDE simulator requires as input. To properly design a grid, the gridder must not only consider the characteristics of the spatial domain, but also the physics of the situation and the peculiarities of the numerical simulator. This paper describes an intelligent gridder that is capable of analyzing the topology of the spatial domain and predicting approximate physical behaviors based on the geometry of the spatial domain to automatically generate grids for computational fluid dynamics simulators. Typically gridding programs are given a partitioning of the spatial domain to assist the gridder. Our gridder is capable of performing this partitioning. This enables the gridder to automatically grid spatial domains of arbitrary configurations. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-24 Title: 5th Quarterly R&D Status Report Author: Saul Amarel Date: December 1994 Abstract: This report covers the first quarter of Year 2 of the "Hypercomputing and Design" (HPCD) project. The broad objective of HPCD is to build on top of advances in massively parallel computing (hypercomputing) and in other areas of computer and computational science [especially in AI and in modeling/ simulation technology] in which the U.S. continues to have substantial strength, and to develop a new generation of engineering automation technology that can bring about dramatic gains in productivity of the national industrial base. Our goal is to develop hypercomputing methods for attaining order-of- magnitude speedups in the time required for transition from a scientific advance to its use in creation of innovative engineering designs and their transition to manufacturing. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-25 Title: Using Feedback To Improve VLSI Designs Author: C.W. Liew Date: February 24th, 1995 Abstract: VLSI HLS design is a typical design optimization problem with a focus on generating good solutions. Typical expert design systems incorporate a large amount of domain knowledge to generate good initial solutions. These systems are unable to use information gleaned from analysis of the solutions (feedback)to generate better solutions. This paper describes a new technique called Constrained-Redo that uses feedback to improve both the power and coverage of an existing design system, the DAA system. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-26 TITLE: Tree codes for vortex dynamics: Application of a programming framework AUTHORS: Sandeep Bhatt, Bellcore and Computer Science Department Pangfeng Liu, Computer Science Department Victor Fernandez, Mechanical and Aerospace Engineering Norman Zabusky, Mechanical and Aerospace Engineering DATE: March 17, 1995 ABSTRACT: This paper describes the implementation of a fast N-body algorithm for the study of multi-filament vortex simulations. The simulations involve distributions that are irregular and time-varying. We adapt our programming framework which was earlier used to develop high-performance implementations of the Barnes-Hut and Greengard-Rokhlin algorithms for gravitational fields. We describe how the additional subtleties involved in vortex filament simulations are accommodated efficiently within the framework. We describe the ongoing experimental studies and report preliminary results with simulations of one million particles on the 128-node Connection Machine CM-5. The implementation sustains a rate of almost 30% of the peak machine rate. These simulations are more than an order of magnitude larger in size than previously studied using direct methods. We expect that the use of the fast algorithm will allow us to study the generation of small scales in the vortex collapse and reconnection problem with adequate resolution. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-27 Abstract: In order to insure efficient and accurate utilization of the NPARC2D code, test computations for a supersonic adiabatic turbulent boundary layer have been performed. The computations have been compared with results obtained using the EDDYBL code of Wilcox which employs the same turbulence model. Author: Song "Sam" Gao Department of Computer Science Rutgers University-The sate University of New Jersey Piscataway, NJ 08855-0909 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-28 ---- abstract ---- Learning When Reformulation is Appropriate for Iterative Design Mark Schwabacher Thomas Ellman Haym Hirsh Gerard Richter Department of Computer Science Rutgers University New Brunswick, NJ 08903 {schwabac, ellman, hirsh, richter}@cs.rutgers.edu HPCD-TR-28 It is well known that search-space reformulation can improve the speed and reliability of numerical optimization in engineering design. We argue that the best choice of reformulation depends on the design goal, and present a technique for automatically constructing rules that map the design goal into a reformulation chosen from a space of possible reformulations. We tested our technique in the domain of racing-yacht-hull design, where each reformulation corresponds to incorporating constraints into the search space. We applied a standard inductive-learning algorithm, C4.5, to a set of training data describing which constraints are active in the optimal design for each goal encountered in a previous design session. We then used these rules to choose an appropriate reformulation for each of a set of test cases. Our experimental results show that using these reformulations improves both the speed and the reliability of design optimization, outperforming competing methods and approaching the best performance possible. (To appear in Workshop of Machine Learning in Engineering at the 14th International Joint Conference on Artificial Intelligence, Montreal, August, 1995.) ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-29 Title: Inductive Learning of Feature-Tracking Rules for Scientific Visualization Authors: Arunava Banerjee Haym Hirsh Thomas Ellman Department of Computer Science Hill Center for the Mathematical Sciences Busch Campus Rutgers, The State University of New Jersey Piscataway, New Jersey 08855 {arunava,hirsh,ellman}@cs.rutgers.edu Abstract: Numerical simulation and scientific visualization are often used by scientists to help them understand physical phenomena. One approach taken by some visualization systems is to identify and quantify coherent features in a simulation and track their trajectories as they evolve over time. Such feature-tracking systems operate either by relying on manual (human) efforts, or by utilizing ad hoc programs embodying heuristics that are computationally expensive to use. Our research demonstrates the use of inductive learning to construct feature-tracking programs for fluid flows. Our approach uses manually generated feature trajectories as training data, and applies inductive learning to construct feature-tracking rules that can then be incorporated into a feature-tracking program. This results in a more efficient system that can match up objects across large time steps without inspecting intermediate steps. We demonstrate our approach on the problem of tracking vortices in turbulent viscous fluids. (To appear in Workshop of Machine Learning in Engineering at the 14th International Joint Conference on Artificial Intelligence, Montreal, August,1995.) Date: April 26th 1995. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-30 Title: Sixth R&D Status Report Author: Saul Amarel Date: January, 1995 Abstract: This report covers the second quarter of Year 2 of the "Hypercomputing and Design" (HPCD) project. The broad objective of HPCD is to build on top of advances in high performance computing (especially in massively parallel and distributed computing), in Artificial Intelligence (AI), in computational science, and in modeling/simulation technology; and to develop a new generation of engineering automation technology that can bring about dramatic gains in productivity of the national industrial base. The top-level goalis to develop methods that effectively exploit High Performance Computing (HPC) for attaining order-of-magnitude speedups in the time required for transition from an innovative design concept, or/and a scientific advance, to a useful high-quality product. The focus of the effort is on design of complex engineering systems (such as electronic chips, computers, ships, jet engines), where the design process is strongly dependent upon the use of knowledge from several scientific disciplines. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-31 Title: Summary Technical Report on Year 1 of the Hypercomputing and Dessign (HPCD) Project Author: Saul Amarel Date: March 1995 Abstract: The primary contractor for this project is Rutgers University. Subcontractors include Princeton University, Cambridge Hydrodynamics, Inc. (CHI), University of Southern California (USC), and Science Applications International Co. (SAIC). The ARPA award for the project provides a total funding of $12.43M over a period of four years. Also, there is substantial cost-sharing by the participating institutions. Other industrial collaborators include staff from IBM, AMD, HP, Micron, LSI, Linoln Labs, Sematech, Intel, Synopsis, UTRC, Boeing, GE, Lockheed, Aerohydro, Proteus Engineering, American President Lines, and Bellcore. This is a multi-disciplinary, "people intensive" project. About 70 investigators, including about 25 graduate students are participants in the project. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-32 Title: Seventh R&D Status Report Author: Saul Amarel Date: June, 1995 Abstract: This report covers the third quarter of Year 2 of the "Hypercomputing and Design" (HPCD) project. The broad objective of HPCD is to build on top of advances in high performance computing (especially in massively parallel and distributed computing), in Artificial Intelligence (AI), in computational science, and in modeling/simulation technology; and to develop a new generation of engineering automation technology that can bring about dramatic gains in productivity of the national industrial base. The top-level goal is to develop methods that effectively exploit High Performance Computing (HPC) for attaining order-of-magnitude speedups in the time required for transition from an innovative design concept, or/and a scientific advance, to a useful high-quality product. The foucs of the effort is on design of complex engineering systems (such as electronic chips, computers, ships, jet engines), where the design process is strongly dependent upon the use of knowledge from several scientific disciplines. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-33 ********************************************************** Title: Numerical simulations of fluid flow in the vocal tract Authors: G. Richard, M.Liu, D. Sinder, H. Duncan, Q. Lin, J. Flanagan, S. Levinson, D. Davis, S. Slimon. Abstract: An alternate approach to speech synthesis based on numerical solution of Navier-Stokes (NS) and Reynolds-Averaged-Navier-Stokes (RANS) equations is described. Unlike the traditional methods based on linear acoustic theory, the NS and RANS formulations are not limited by the assumptions of linearity, negligible viscous effects, and plane wave propagation. In the present formulation, the Navier-Stokes equations are discretized and solved using a finite difference method. Initial applications involve 2-D simulations of flow through ideal channels (straight or curved tubes) with rigid walls and constant boundary conditions (constant flow velocity at inlet, zero pressure at outlet). As expected for simple geometries, the resonance frequencies correspond to those predicted by linear acoustics. It is also shown that for curved tubes, there is an effect of curvature on frequencies above 5 kHz. In another application, the formulation is applied to the geometry of the three cardinal vowels. Periodic inflow boundary conditions are also used (a train of short pulses to represent vocal cord excitation). Synthetic speech sounds of encouraging quality are obtained for the three vowels. [Research supported by NSF/ARPA IRI-9314946 and ARPA DAST 63-93-C-0064]. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-34 Using Modeling Knowledge to Guide Design Space Search Andrew Gelsey, Mark Schwabacher and Don Smith January 1996 Automated search of a space of candidate designs seems an attractive way to improve the traditional engineering design process. To make this approach work, however, the automated design system must include both knowledge of the modeling limitations of the method used to evaluate candidate designs and also an effective way to use this knowledge to influence the search process. We suggest that a productive approach is to include this knowledge by implementing a set of model constraint functions which measure how much each modeling assumptions is violated, and to influence the search by using the values of these model constraint functions as constraint inputs to a standard constrained nonlinear optimization numerical method. We test this idea in the domain of conceptual design of supersonic transport aircraft, and our experiments indicate that our model constraint communication strategy can decrease the cost of design space search by one or more orders of magnitude. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-35 Title: Eighth R&D Status Report Author: Saul Amarel Date: September 1995 Abstract: The second annual HPCD Workshop took place on July 20 and 21, 1995 at Rutgers. The objective of the workshop was to review the status and directions of HPCD research; and to bring together all the project investigators and affiliates, the ARPA PM and other ARPA people close to the project, members of the HPCD Technical Advisory Committee, and selected "friends of the project" from academia, industry and government - to discuss ongoing technical work in all areas of the project, to strengthen colaborations and to review plans for future work. In addition to technical presentations, there was a project review meeting which involved the PI, co-PIs, area coordinators, members of the Technical Advisory Committee who were present at the Workshop (Dr. Raymond Cosner, Dr. Malvin Kalso), Dr. Hiro Miura, who is the PM on a closely related NASA grant, and our ARPA PM (Robert Lucas). Dr. Joseph Seneca (Univeristy VP for Academic Affairs) welcomed the workshop on behalf of the university, and Robert Lucas spoke at the workshop dinner. Perhaps the most important conclusion from the Workshop was that, in addition to making substantial technical progress in all of the Areas, the HPCD project has led to high levels of cross-disciplinary interaction. One example is the interactions between experts in hydrodynamics, AI/design, parallel processing, and visualization, all working on the ship design problems. Another example is the ground breaking work on design of inlets for jet engines, a project that became possible because of the interactions within HPCD between HPCD researchers in aerodynamics and AI/design. Feedback from the Technical Advisory Committee and other outside observers stressed the rarity and importance of this sucess in fostering interdisciplinary work. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-36 Automated Redesign of the NASA P8 Hypersonic Inlet Using Numerical Optimization Vijay Shukla, Andrew Gelsey, Mark Schwabacher, Donald Smith, and Doyle D. Knight November 1995 The NASA P8 hypersonic inlet has been redesigned using an automated methodology incorporating a 3-D Reynolds-averaged Navier-Stokes code, a gradient-based optimizer and artificial intelligence methods. The objective of the redesign is to cancel the cowl shock and the additional cowl-generated compression at the centerbody by appropriate contouring of the centerbody boundary. The original P8 inlet, designed in the early 1970s, was intended to achieve this same objective, but detailed experimental measurements indicated that a substantial reflected shock system was present. We have obtained several different redesigns which achieve approximate cancelation of the cowl shock and additional cowl-generated compression. The choice of the objective function, which is used to drive the optimization, has a significant impact on the final design. Several different formulations for the objective function have been employed, and improvements of 60% to 80% have been achieved. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-37 Title: Intelligent Automated Grid Generation for Numerical Simulations Author: Ke-Thia Yao, Andrew Gelsey Abstract: Numerical simulation of partial differential equations (PDEs) plays a crucial role in predicting the behavior of physical systems and in modern engineering design. However, in order to produce reliable results with a PDE simulator, a human expert must typically expend considerable time and effort in setting up the simulation. Most of this effort is spent in generating the grid, the discretization of the spatial domain which the PDE simulator requires as input. To properly design a grid, the gridder must not only consider the characteristics of the spatial domain, but also the physics of the situation and the peculiarities of the numerical simulator. This paper describes an intelligent gridder that is capable of analyzing the topology of the spatial domain and of predicting approximate physical behaviors based on the geometry of the spatial domain to automatically generate grids for computational fluid dynamics simulators. Typically gridding programs are given a partitioning of the spatial domain to assist the gridder. Our gridder is capable of performing this partitioning. This enables the gridder to automatically grid spatial domains with a wide range of configurations. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-38 Intelligent Gradient-Based Search of Incompletely Defined Design Spaces Mark Schwabacher Andrew Gelsey Gradient-based numerical optimization of complex engineering designs offers the promise of rapidly producing better designs. However, such methods generally assume that the objective function and constraint functions are continuous, smooth, and defined everywhere. Unfortunately, realistic simulators tend to violate these assumptions. We present a knowledge-based technique for intelligently computing gradients in the presence of such pathologies in the simulators, and show how this gradient computation method can be used as part of a gradient-based numerical optimization system. We tested the resulting system in the domain of conceptual design of supersonic transport aircraft, and found that using knowledge-based gradients can decrease the cost of design space search by one or more orders of magnitude. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-4 Title: Scheduling of Structured and Unstructured Computation Author: A. Gerasoulis, J. Jiao, T. Yang Date: April, 1994 Abstract: Automatic scheduling has been shown to be practical for parallel machines with a small number of processors. However, the practicality of scheduling for scalable machines with a large number of processor still remains an open research area. The purpose of this paper is to investigate the applicability of scheduling on scalable architectures where communication cost is significant. We have built a system named PYRROS that schedules task graphs and also generates parallel code based on the scheduling result. We report on experiments performed on the NCUBE-2, a scalable parallel distributed architecture, using common application programs, including the dense Gaussian and Gauss Jordan Elimination algorithms, sparse matrix computation, fast fourier transforms and fast hierarchical algorithms for 2D N-body simulations. These preliminary experiments have produced very promising results with regard to the practicality of automatic scheduling for scalable architectures. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-40 Title: Intelligent Intercessors in Analysis Models for Automated Design Authors: J. Keane and T. Ellman Abstract: Systems for automated design optimization of complex real-world objects can, in principle, be constructed by combining domain-independent numerical codes with existing domain-specific analysis and simulation models. Unfortunately, existing ``legacy'' analysis models are frequently unsuitable for use in automated design. They may crash for large classes of input, be numerically unstable or locally non-smooth, or be highly sensitive to control parameters. Direct modification of legacy codes to correct these problems is often rendered infeasible by the high cost of re-validating the modified code. This paper describes an approach to incorporating knowledge-based handling of failures into design optimization systems that does not require code modification, yet allows for fine-grained control of model execution. We have constructed a toolkit for the development of robust design optimization systems that builds ``intelligent intercessors'' into existing analysis models. These intercessors are compiled from high-level rules to code that is inserted between discretely callable components of the design system. Intercessors serve to detect failures; take corrective action when possible; and transfer control to an appropriate destination when corrective actions fail. We show that this approach is effective in improving analysis model robustness and design optimization performance in the domain of conceptual design of jet engine nozzles. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-41 Title: Extensions to the Franz, Inc.'s Allegro Common Lisp Foreign Function Interface Author: J. Keane Abstract: As provided by Franz, Inc., the foreign function interface of Allegro Common Lisp has a number of limitations. This paper describes extensions to the interface that facilitate the inclusion of C and Fortran code into Common Lisp systems. In particular, these extensions make it easy to utilize libraries of numerical subroutines (such as those from Numerical Recipes in C) from within ACL, including those routines that take functions as arguments. A mechanism for creating Lisp-like dynamic runtime ``closures'' for C routines is also described. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-42 A Transformation System for Interactive Reformulation of Design Optimization Strategies Thomas Ellman John Keane Takahiro Murata Mark Schwabacher Department of Computer Science, Hill Center for Mathematical Sciences Rutgers University, Piscataway, New Jersey 08855 {ellman,keane,murata,schwabac}@cs.rutgers.edu HPCD-TR-42 November 1995 Numerical design optimization algorithms are highly sensitive to the particular formulation of the optimization problems they are given. The formulation of the search space, the objective function and the constraints will generally have a large impact on the duration of the optimization process as well as the quality of the resulting design. Furthermore, the best formulation will vary from one application domain to another, and from one problem to another within a given application domain. Unfortunately, a design engineer may not know the best formulation in advance of attempting to set up and run a design optimization process. In order to attack this problem, we have developed a software environment that supports interactive formulation, testing and reformulation of design optimization strategies. Our system represents optimization strategies in terms of second-order dataflow graphs. Reformulations of strategies are implemented as transformations between dataflow graphs. The system permits the user to interactively generate and search a space of design optimization strategies, and experimentally evaluate their performance on test problems, in order to find a strategy that is suitable for his application domain. The system has been implemented in a domain independent fashion, and is being tested in the domain of racing yacht design. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-43 Reformulation of Design Optimization Strategies Thomas Ellman John Keane Takahiro Murata Arunava Banerjee Department of Computer Science, Hill Center for Mathematical Sciences Rutgers University, Piscataway, New Jersey 08855 {ellman,keane,murata,arunava}@cs.rutgers.edu HPCD-TR-43 January 1996 Automatic design optimization is highly sensitive to problem formulation. The choice of objective function, constraints and design parameters can dramatically impact the computational cost of optimization and the quality of the resulting design. The best formulation varies from one application to another. A design engineer will usually not know the best formulation in advance. We have therefore developed a system that supports interactive formulation, testing and reformulation of design optimization strategies. Our system includes an executable, second-order data-flow language for representing optimization strategies. The language allows an engineer to define multiple stages of optimization, and to specify the design parameters, constraints and objectives to be handled at each stage. We have also developed a set of transformations that reformulate strategies represented in our language. The transformations can approximate objective and constraint functions, define new constraints, and re-parameterize or change the dimension of the search space, among other things. The system is applicable to design problems in which the artifact is governed by algebraic or ordinary differential equations. We have tested the system on problems of racing yacht and jet engine nozzle design. We report experimental results demonstrating that our reformulation techniques can significantly improve the performance of automatic design optimization. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-44 Multi-Level Modeling for Engineering Design Optimization Thomas Ellman John Keane Mark Schwabacher Ke-Thia Yao Department of Computer Science, Hill Center for Mathematical Sciences Rutgers University, Piscataway, NJ 08855 {ellman,keane,schwabac,kyao}@cs.rutgers.edu HPCD-TR-44 June 1996 Physical systems can be modeled at many levels of approximation. The right model depends on the problem or subproblem to be solved. In many cases, a combination of models will be more effective than a single model alone. Our research investigates this idea in the context of engineering design optimization. We present a family of strategies for using multiple models to optimize engineering designs. The strategies are useful when multiple approximations of an objective function can be implemented by compositional modeling techniques. We show how a compositional modeling library can be used to construct a variety of locally calibratable approximation schemes that can be incorporated into the optimization strategies. We analyze the optimization strategies and approximation schemes to formulate and prove sufficient conditions for correctness and convergence. We also report experimental tests of our methods in the domain of sailing yacht design. Our results demonstrate a dramatic reduction in the CPU time required for optimization, with no significant loss in design quality. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-45 The Use of Artificial Intelligence to Improve the Numerical Optimization of Complex Engineering Designs Mark Schwabacher Ph.D. Thesis Rutgers University October, 1996 Abstract: Gradient-based numerical optimization of complex engineering designs promises to produce better designs rapidly. However, such methods generally assume that the objective function and constraint functions are continuous, smooth, and defined everywhere. Unfortunately, realistic simulators tend to violate these assumptions. We present several artificial intelligence-based techniques for improving the numerical optimization of complex engineering designs in the presence of such pathologies in the simulators. We have tested the resulting system in several realistic engineering domains, and have found that using our techniques can greatly decrease the cost of design space search, and can also increase the quality of the resulting designs. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-49 Title: Knowledge-based Management of Legacy Codes for Automated Design" Author: John Keane (Thesis) - HPCD-TR-49 Abstract Systems for automated design optimization of complex real-world objects can, in principle, be constructed by combining domain-independent numerical routines with existing domain-specific analysis and simulation programs. Such ``legacy'' analysis codes are frequently unsuitable for use in automated design. They may crash for large classes of input, be locally non-smooth, or be highly sensitive to control parameters. To be useful, analysis programs must first be modified to reduce or eliminate only the undesired behaviors, without altering the desired computation. To do this by direct modification of the programs is labor-intensive, and necessitates costly re-validation. This dissertation describes research into how legacy analysis codes can be usefully employed in design automation systems. We show that recovery from failure is possible when the failure occurs in the context of a search-based process such as optimization. We discuss the importance of failure context in determining the correct failure recovery action. We then describe an approach to failure recovery that is both context-sensitive and guarantees the integrity of the original computation to which it is applied. We have implemented a high-level language and run-time environment (together called LCM) that allow context-sensitive failure-handling strategies to be incorporated into existing Fortran and C analysis programs while preserving their computational integrity. Our approach relies on globally managing the execution of these programs at the level of discretely callable functions so that the computation is only affected when problems are detected. Problem handling procedures are constructed from a knowledge base of generic problem management strategies. We show that our approach is effective in improving analysis program robustness and design optimization performance in several real-world design domains. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-5 Title: 2ND QUARTERLY R&D STATUS REPORT Author: Saul Amarel Date: April, 1994 Abstract: Thsi report covers the second quarter of the "Hypercomputing and Design" (HPCD) project. Activities initiated during the previous period of the project have gained additional momentum - in terms of group building, strengthening of collaborative links, a better definition of planned research directions, the identification of new research opportunities, and also in terms of specific results. Of special note is the growth/strengthening of collaborative links between investigators from various disciplines and organizational affiliations - each bringing adifferent viewpoint and different methods and tools to the handling of the same research problem. This is clearly in line with the type of synergy and leverage that we believe is needed for making serious progress in HPC and in its application to complex science-based engineering design. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers. edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-50 Title: Guided Crossover: A New Operator for Genetic Algorithm Based Optimization Authors:Khaled Rasheed and Haym Hirsh HPCD-TR-50 Genetic algorithms (GAs) have been extensively used in different domains as a means of doing global optimization in a simple yet reliable manner. They have a much better chance of getting to global optima than gradient based methods which usually converge to local sub optima. However, GAs have a tendency of getting only moderately close to the optima in a small number of iterations. To get very close to the optima, the GA needs a very large number of iterations. Whereas gradient based optimizers usually get very close to local optima in a relatively small number of iterations. In this paper we describe a new crossover operator which is designed to endow the GA with gradient-like abilities without actually computing any gradients and without sacrificing global optimality. The operator works by using guidance from all members of the GA population to select a direction for exploration. Empirical results in two engineering design domains and across both binary and floating point representations demonstrate that the operator can significantly improve the steady state error of the GA optimizer. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-59 Title: Highest Utility First Search: a Control Method for Multi-level Stochastic Design Authors: L. Steinberg, J. Hall and B. Davison E-Mails: lou, davison@cs.rutgers.edu HPCD-TR-59 Abstract: An intrinsic characteristic of stochastic optimization methods, such as simulated annealing, genetic algorithms and multi-start hill climbing, is that they can be run again and again on the same inputs, each time potentially producing a different answer. When such algorithms are used in a design process with multiple levels of abstraction, where the output of one stochastic optimizer becomes the problem statement for another stochastic optimizer, we get an implicit tree of alternative designs. After each optimizer run we face a control problem of which level's optimizer to run next, and which design alternative to run it on. This problem is made more difficult by the fact that we generally can get a precise evaluation of the design alternatives only at the lowest level (the final results), and must make do at higher levels with only an estimate of how good a final design each alternative will lead to. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-6 Title: A Navier-Stokes Algorithm for Turbulent Flows Using an Unstructured Grid and Flux Difference Splitting Authors: F. Jacon and D. Knight Date: May, 1994 Abstract: An algorithm has been developed for the two-dimensional Reynolds- Averaged Navier-Stokes equations. The effects of turbulence are modelled by the standard k - e model of Launder and Spalding. The equations are solved using an unstructured grid of traingles with the flow variables stored at the centroids of the cells. The treatment of the inviscid fluxes is performed with Roe's flux difference split method. Turbulent and viscous stresses and heat transfer are obtained from a discrete representation of Gauss's theorem. For the inviscid fluxes, linear reconstruction of the flow variables to the cell faces provides second-order spatial accuracy. Interpolation of the flow variables to the nodes is achieved using a second-order accurate method. A four stage modified Runge-Kutta scheme is employed for the temporal integration providing second-order accuracy in time. The algorithm is appleid to an incompressible turbulent far wake, a supersonic turbulent mixing layer and boundary layers over flat plates at Mach numbers of 0.1 and 2.0 using laws of the wall as boundary conditions. Results are in excellent agreement with previous computations. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers. edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-7 Title: Third Quarterly R&D Status Report Author: Saul Amarel Date: June, 1994 Abstract: This report covers the third quarter of the "Hypercomputing and Design" (HPCD) project. Activities initiated during the previous two periods of the project have gained additional momentum. Special efforts were made to strengthen collaborative links between research areas. The project is gaining more cohesiveness as research directions are becoming better defined in light of the overall project theme. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-8 Title: DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors Author:T. Yang and A. Gerasoulis Date: September, 1994 Abstract: We present a low complexity heuristic named the Dominant Sequence Clustering algorithm (DSC) for scheduling parallel tasks on an unbounded number of completely connected processors. The performance of DSC is comparable or even better on average than other higher complexity algorithms. We assume no task duplication and nonzero communication overhead between processors. Finding the optimum solution for arbitrary directed acyclic task graphs (DAGs) is NP-complete. DSC finds optimal schedules for special classes of DAGs such as fork, join, coarse grain trees and some fine grain trees. It guarantees a performance within a factor of two of the optimum for general coarse grain DAGs. We compare DSC with three higher complexity general scheduling algorithms: the ETF by Hwang, Chow, Anger and Lee[11], Sarkar's clustering algorithm[17] and the MD by Wu and Gajski[19]. We also give a sample of important practical applications where DSC has been found useful. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: HPCD-TR-9 Title: 1st Annual Project Summary Author: Saul Amarel Date: September, 1994 Abstract: The broad objective of HPCD is to build on top of advances in massively parallel computing (hypercomputing), in AI, and in modeling/ simulation technology, and to develop a new generation of engineering automation technology that can bring about dramatic gains in productivity of the national industrial base. The top-level goal is to develop hypercomputing methods for attaining order-of-magnitude speedups in the time required for transition from an innovative design concept, or/and a scientific advance, to a useful high-quality product. The focus of the effort is on design of complex engineering systems (such as computers, ships, jet engines), where the design process is strongly dependent upon the use of knowledge from several scientific disciplines. NOTE: The text of this report is not currently available via internet. To obtain a copy, please send electronic mail to techreport@cs.rutgers.edu. :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::