Search

Near the end of my sabbatical year in Sydney Australia, I received e-mail from Bashar Nuseibeh, asking me to write a desert island column. This column asks what I would bring, or consider essential, if marooned on a deserted island. The book selection process turns out to be an intriguing search, sort, and knapsack problem. The search takes place in the domain of relevant books. Relevancy is a philosophical determination reflecting my personal history and my view of the future. Sorting uses relevancy to prioritize these books. The knapsack problem occurs with the notion of maximizing utility in the future within the editorial constraints. Ironically, I had gone through just this kind of activity when I packed for my sabbatical year. I was limited to what I could bring with me to Australia both by the ruinous cost of shipping and the airline travel allotment.

An adaptable tool generator, utilizing a knowledge-based automatic program synthesis architecture, allows the user to tailor the tool implementation to the demands of the application. An implementation of the knowledge-based program synthesis architecture, ELF, indicates the feasibility of this approach. We review the use of domain knowledge to synthesize CAD router software.

A constraint-driven, real-time software synthesis architecture called RT-Syn is described. RT-Syn formulates design space constraints for each task in the real-time software system from timing requirements and a behavior description. RT-Syn then uses these constraints within a simulated-annealing-like approach, selects an abstract implementation for every data structure and algorithm required to implement the desired behavior, and transforms these selections into executable code. Experimental results covering the synthesis of two real-time software tasks that meet the desired constraints are presented. These results illustrate the effectiveness of the simulated-annealing-like approach in searching the software design space and the high reusability and maintainability provided by the use of synthesis technology. >

This paper presents research into the automation of design phase software synthesis. Key features of an application domain, real-time multi-tasking software, are incorporated into a design selection heuristic. This heuristic captures the mathematical underpinnings inherent in the domain. A design phase synthesis algorithm, incorporating the design selection heuristic, is described. This paper then illustrates this algorithm's ability to synthesize the design of a real-time multi-tasking software set. >

This paper presents an overview of a distributed embedded system design assistant called Systems Engineers Workbench (SEW 2.0). SEW 2.0 uses a suite of design frameworks, with supporting representations, to structure the inherent complexity. A set of design assist operatives further improves the ability of the designer to explore the domain space while evaluating performance/resource tradeoffs.

Introduction H. Reubenstein, D. Setliff. Searching for a Global Search Algorithm S. Dick, T. Santen. Specification and Animation of a Bank Transfer Using KIDS/VDM Y. Ledru. Interactive Explanation of Software Systems W.L. Johnson, A. Erdem. Test Case Generation as an AI Planning Problem A. Howe, R. Mraz. Desert Island Column W. Turski.

The Selection Stage chooses the appropriate data structures and router algorithms to implement the required routing tasks given the preliminary problem description produced by the Input Stage. Note, however, that one algorithm choice does not comprise an entire router. Indeed, there exists tens of possibilities for each of the many algorithms and data structures comprising a real router that matches any typical user specification. Hence, decision-making in this stage requires information on such topics as data structure capabilities, data structure efficiencies, and algorithm suitability. This stage integrates the router structure knowledge, router phase requirement knowledge, data structure implementation knowledge and design interaction knowledge sources to select and refine implementation candidates for both data structures and algorithms.

The output Code Generator Stage produces the executable code for the router. It takes as input the final candidate selections of algorithm schemas represented in ADL, and data structures represented as hierarchical compositions of simple templates. The Selection Stage produces these selections. Interestingly enough, the final candidate selections, while fully specifying a router at the design task and subtask level, do not completely specify an implementation of the router. The Code Generator Stage still must apply domain knowledge during transformation and synthesis of appropriate algorithms to produce the desired router code. The code generation process is based on a transformational approach, in which a sequence of stepwise refinements [5] ultimately lead to executable code, in this case, code written in C. The transformation process uses design generation knowledge, design interaction knowledge, and program synthesis knowledge.

ELF is a program architecture: an organization of synthesis strategies aimed at transforming an abstract, non-executable description of a software tool into real, working software. Although ELF relies on many program synthesis ideas, the real focus of the ELF prototypes is to illustrate the feasibility of integrating domain knowledge and program synthesis knowledge for the automatic generation of real-world application tools. Maze routers are our target application domain. However, it is important to understand that ELF is a prototype. We do not expect to be able to generate a perfectly tuned, perfectly customized, high-performance router; rather our intent is to demonstrate the feasibility of automatically generating tools. Hence, we intend to focus on the construction of “reasonably functional and efficient” routers from only a high-level description of the routing task and from domain knowledge. As we shall see in subsequent chapters, we measure success by our ability to generate and demonstrate such routers, and to retarget the ELF generator to different maze router variants. Producing routers over a variety of technologies illustrates how this architecture copes with shifting technology environments. This chapter introduces the major components of the ELF architecture, and the basic synthesis strategies and representation schemes used by ELF.

The Input Stage takes as input a user specification template consisting of a set of technology constraints and produces the problem description used in the Selection Stage. This problem description consists of an ordered set of tasks and subtasks that define the router design process. For each task, the Input Stage generates a set of candidate solution options. These options correspond to ADL algorithm representations or to data structure representations. Options are generated by applying router domain knowledge to the user specification. This chapter discusses some operational issues, the types of knowledge used, and examples of typical rules in the Input Stage.

Our work on program synthesis is targeted at a particular VLSI CAD problem: wire routing. We focus on a particular class of routing tools called maze routers. This chapter describes the actions of routers in general and maze routers in particular, and then reviews the relevant mechanics of maze routing systems. Maze routing algorithms have been applied to a variety of wire routing problems. Varying “environmental” constraints strongly affect a router’s implementation. As evidence of this dependency on environmental constraints, we organize the constraints into three fields: algorithm, application, and fabrication constraints. We then describe the effects of modifying various constraints within these fields.