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.

This paper describes how simulated annealing can be used to synthesize software implementations. Simulated annealing is a strategy for solving combinatorial optimization problems. The challenge here is to effectively cast the many implementation decisions (e.g., data structures, algorithms, data flow) inherent in implementing software systems as an optimization problem. This paper presents RT-Syn, a software synthesis architecture targeting real-time software. Real-time software is characterized by a set of tasks, each with individual hard timing deadlines. RT-Syn represents implementation decisions in terms of their timing and space costs and then uses simulated annealing to minimize the cost of the implementation until the individual hard timing deadlines are met. Producing a satisficing implementation rather than an absolute optimal implementation results in tractable annealing run times. We present experimental results covering the synthesis of real-time software tasks that meet the desired execution characteristics. These results illustrate the effectiveness of the simulated annealing approach in searching the software implementation space and the belief that simulated annealing approaches have much to offer to automated software engineering.

Software synthesis techniques provide most, but not all, of the functionality in Fischer's DODE. Software synthesis is achievable and is best at the automation of repetitive activities, even when these activities are design. Software synthesis performs analysis and synthesis activities automatically in well-known domains, while in less well-known domains, software synthesis supports simulation activities for human cooperation. Software synthesis techniques support human cooperation by effectively evaluating different options within the design space. Current software synthesis architectures are well on their way towards instantiating Fischer's DODE design process.