Design of SYMPHONY

SYMPHONY was designed with two major goals in mind--portability and ease of use. With respect to ease of use, we aimed for a ``black box'' design, whereby the user would not be required to know anything about the implementation of the library, but only about the user interface. With respect to portability, we aimed not only for it to be possible to use the framework in a wide variety of settings and on a wide variety of hardware, but also for it to perform effectively in all these settings. Our primary measure of effectiveness was how well the framework would perform in comparison to a problem-specific (or hardware-specific) implementation written ``from scratch.''

It is important to point out that achieving such design goals involves a number of very difficult tradeoffs. For instance, ease of use is quite often at odds with efficiency. In several instances, we had to give up some efficiency to make the code easy to work with and to maintain a true black box implementation. Maintaining portability across a wide variety of hardware, both sequential and parallel, also required some difficult choices. For example, solving large-scale problems on sequential platforms requires extremely memory-efficient data structures in order to maintain the very large search trees that can be generated. These storage schemes, however, are highly centralized and do not scale well to large numbers of processors.

Ted Ralphs