Site Home : Research : Master's Thesis : One Chapter
Bringing together information that is today in separate programs or on separate pieces of paper is fundamentally powerful by itself. A planning program with hydrology data can trivially warn the user that a proposed excavation will become flooded if there is any rain. Keeping track of utility lines, especially gas lines, during both design and construction can save lives as well as millions of dollars.
It is important to distinguish between raw geometry, the kind of data in traditional CAD systems, and full-fledged objects. Raw geometry consists of lines, text, polygons, circles, etc. that together communicate something meaningful to a human user. Full-fledged objects represent their real-world counterparts in a sufficiently rich manner to permit computation about real-world situations. For example, a raw geometry line/text combination that communicates "gas line" is nice to have on a blueprint, but only an object of the class GAS-LINE can conceivably cause a backhoe-operator assistant program to declare a full red alert when there is a risk of explosion.
Once comprehensive site databases are available, analysis algorithms will grow to take advantage of the data. Without the data, nobody will bother to write software.
Because a core dump saves everything that has been added to or changed in the memory since Lisp was started, this approach is extremely wasteful of disk space. Cooperation is difficult as well. If Rebecca is working on a design on one workstation, Rachel is unable to add anything to Rebecca's design from another workstation. Rachel would have to come in at night and work on Rebecca's memory image. Finally, a core dump made on a computer using, for example, a 68000 microprocessor might become unusable if users switched to computers using a RISC processor with a different format for numbers.
Writing everything into a "moby file" (from Moby Dick) is a somewhat better approach and this is what SITE CONTROLLER presently does. Users can recover the exact state of the system when the moby file was written, just as they did by restarting a core dump. Only essential data need be stored and therefore a moby file may be kept to a reasonable size. Furthermore, different sites may be stored in different moby files so that comparing projects is as simple as reading in multiple files. Machine independence is also achievable.
Despite these advantages, moby files retain many of the core dump's drawbacks. First, Rebecca and Rachel still can't cooperate effectively. Rebecca must write a file then wait for Rachel to read it, work on the design, and write it back to disk before she can work again. Second, all the data concerning a project must be read even if only a tiny amount is needed. As site models grow to tens of megabytes, this may dramatically affect performance. Third, no consistent journal is kept of how the design evolved. Except by laborious byte-by-byte comparison of moby files, there is no way to determine who changed what, or when and why.
Concurrency control prevents simultaneous updates by multiple users from interfering with one another. Ensuring that updates occur in a controlled manner and that the data remain consistent have been primary DBMS concerns since the late 1960's, when computerized airline reservation systems were developed. Reading and writing to the database are restricted to take place during atomic transactions. The DBMS ensures that if a transaction cannot be completed for any reason, the database remains unchanged from the way it was before the transaction commenced. When a record is to be updated, the transaction first gets a lock, changes the record, then releases the lock. While Rebecca's transaction holds a lock on a record, Rachel's attempt to update is blocked. It is possible for Rebecca's transaction to be blocked waiting for a lock held by Rachel's transaction that is blocked waiting for a lock held by Rebecca's transaction. This results in a deadlock, and deadlock detection facilities generally abort one or both transactions involved.
Skillful exploitation of standard DBMS concurrency-control facilities and techniques by a CAE system enables users to cooperate on projects. Rachel can "check out" a portion of the design and work on it while Rebecca works on some other aspect of the problem. If Dina tries to make changes to Rachel's portion, the database tells her to wait until Rachel has "checked in" her changes. When Rachel checks in her solution, Rebecca and Dina's working copies are updated to reflect Rachel's changes.
Because the first DBMS applications were financial, keeping a transactions log has always been a built-in defense against hardware and software unreliability. A journal of transactions is kept and therefore the state of the database at any time is recoverable so long as an initial state and the transactions journal are retained.
Commercial DBMS devote much attention to query mechanisms. Business problems require frequent extraction of tiny bits of information from vast databases. The quest for greater ease of specifying which data are required has spawned hundreds of query languages. Query optimization algorithms and even special hardware have been designed to improve database performance. CAE data stored in a commercial DBMS may be easily and efficiently accessed even in ways not foreseen by the original system designers.
In the mid-1960's, IBM developed the hierarchical data model where everything is organized into trees. A family's genealogy would fit nicely into the hierarchical model. However, if one wanted to also keep track of all family picnics and which of the family members had attended each one, one would be forced to construct additional trees to represent that information. To avoid duplicating records in these multiple trees and to facilitate the representation of complex relationships, hierarchical database systems incorporate a variety of kludges, notably virtual records.
GE developed what became the network data model at roughly the same time. Data is represented in a directed graph, with each one-way link signifying a relationship between two pieces of data. The family picnic example above can be represented more or less directly, although one additional record must be introduced for each link.
Both the network and the hierarchical models require the programmer to have knowledge of the graph or tree structure. Queries are procedural, instructing the DBMS to traverse one link after another. This makes programs hard to write and obscures their meaning. The relational data model [Codd 1970] lends itself to declarative query languages. Instead of specifying how to do something, the user need only specify what is wanted. Relational algebra is a consistent set of operations on relations whose results are themselves relations. Because these operations are closed under the set of relations they may be freely composed.
Relational algebra has been the basis of many query languages for relational DBMS. Of the relational languages, SQL, developed in the late 1970's by IBM, has become the most popular. SQL was intended to meet the needs of both interactive non-programmers users and experienced programmers and hence does not fully satisfy either type of user: SQL cannot be the world's best interactive query language and also an elegant data manipulation sublanguage for conventional programming languages. Furthermore, when SQL is grafted into host languages, its syntax and model of computation often strike a discordant note. SQL itself is more limited in power than standard programming languages. One could not, for example, write a CAE system in SQL. Instead, a CAE system written in Lisp would include some embedded SQL commands to be handed off to the DBMS.
Declarative queries, ease of use, and flexibility in relational databases were initially achieved at the price of sluggish performance. However, advances in query optimization and computer hardware have made relational databases the most practical solutions for most business problems in the early 1990's. Unfortunately, the systems remain orders of magnitude too slow to be used by CAE programs.
Many excellent textbooks serve to educate the future archivists of corporate America in the art of database management [Elmasri and Navathe 1989; Ullman 1988]. Examples of ways in which geometric models can be stored in different types of databases are contained within [Kemper and Wallrath 1987].
Computer-aided engineering gives rise to complex objects and relationships that must be described obliquely in standard database systems. Information associated with an object is often spread around in the database and thus reading an object from disk entails multiple seeks. Since a disk seek takes as long as one million processor operations, minimizing disk seeks is the central goal when striving for high-performance database systems.
Transactions in CAE systems can take hours and may involve megabytes of data. Consider the following example: supply a surface to an analysis algorithm, wait for the water flow over the surface to be calculated, present that analysis to an engineer for annotation, and finally write everything back into the database so that other engineers can use the results to keep structures out of the way of floods. Conversely, transactions in CAE systems might take microseconds. For example, dragging a mouse across a screen might result in changes to dozens of portions of the site model and it might be nice to handle those changes as database transactions in order to capture the benefits of concurrency and version control. If Rachel and Rebecca were working closely together, it might be desirable to synchronize their activities through the database so that every time Rebecca dragged something around with the mouse, Rachel would see the effects on her screen.
Schema modification is a routine occurrence in a CAE system. An engineer may decide that a new type of building block is required, or that objects never before linked should be associated now. The diversity of the construction industry ensures that computer-aided earthmoving will require flexibility in database schema. If a job demands working with asbestos, a foreman might need to store information about which workers smoke cigarettes so that the computer would be able to automatically keep them away from risky positions around the site.
Numerous object-oriented database management systems (ODMS) have been developed recently [Cattell 1991; Bertino and Martino 1991] that are much more suitable than traditional business-oriented database systems. At a minimum, an ODMS provides for object grouping, storing in one place all the data that pertain to one real-world or abstract entity, and object identity, unique ID pointers for objects that are independent of the values contained within those objects. Most systems are attempts to make persistent the object-oriented features available ephemerally in C++, Common Lisp Object System, and Smalltalk. Consequently, these object-oriented databases offer the same class definition, inheritance, method definition, and instance variable storage features of the object-oriented programming language. Ancillary query languages and database administration tools may be included, but fundamentally object-oriented databases do not require programmers to learn new data-manipulation languages.
Typifying the best of the new systems is ObjectStore [Lamb 1991]. ObjectStore exploits existing virtual memory hardware and operating system support to gain high performance and transparency to existing software. Persistent objects on disk are represented bit-for-bit identically to transient C++ objects in memory. This kind of technique has been used by at least four commercial products and is called the disk-image method. The entire relevant portion of the database in mapped into the user process's virtual memory space. Accessing an object for the first time takes as much time as handling a page fault, i.e., mostly however long it takes to load the page from the local disk or from across the network. Subsequent reads or writes to a persistent object occur at normal memory speed. Pointers to objects are ordinary address space pointers. ObjectStore is able to handle databases substantially larger than standard virtual memory address spaces, but the extra long pointers are not visible to user programs. Note that the authors of ObjectStore were able to save themselves the trouble of writing a data caching system--they get it for free from the operating system's virtual memory code, which will strive to keep the data that is most likely to be needed in memory at all times.
Programs save time and programmers save effort with this architecture for several reasons. First, no translation need be performed between the database representation and the in-memory representation. Second, standard library procedures may be used without even recompilation to manipulate database objects. As far as the library procedure is concerned, it is just reading to or writing from data structures in memory. Third, pointers to objects are dereferenced by virtual memory hardware in nanoseconds, rather than being translated by software in microseconds. Finally, the virtual memory system already contains hardware and software support for determining which pages have been modified and need to be written back to disk.
Rather than locking individual objects, ObjectStore locks virtual memory pages. Thus, hundreds of objects may be locked with a single swift operation. Although one might conjecture that this would lead to pointless concurrency conflicts since some unneeded objects are locked along with the ones that will actually be updated, in reality the system is speeded up so much by not having to keep track of thousands of separate locks that transactions execute faster and hence are less likely to conflict.
Ultimately, any choice among databases must take performance into account. After all, any database management system is capable of supporting any task given a fast enough computer and enough extra work by the programmer user. However, in the real world, substantially more efficient execution makes the difference between a practical solution and an interesting bit of research. Benchmarks on the kinds of pointer-chasing done by object-oriented programs show that ODMSs in general are about 100 times faster than relational databases and that there are significant performance differences among ODMS products [Cattell and Skeen 1992].
Although ObjectStore solves many problems faced by CAE programmers, it also serves to illustrate some of the shortcomings of ODMSs. Using the disk-image approach yields dramatic performance improvements but exacts a penalty in data integrity. A program that can inadvertently modify any memory location is now capable of inadvertently corrupting the database. Anyone who has ever used a C program on a personal computer that mistakenly wrote over the operating system and crashed the machine would probably have reservations about a C++ program managing critical financial data in ObjectStore. (Note: there are disk-image object databases, such as O2, that use the disk-image approach but achieve high data integrity by supporting inherently safer languages, such as Lisp and Smalltalk.)
Just as C++ is a throwback to the computer languages of the 1960's and 1970's, ObjectStore in some ways dredges back up limitations of hierarchical and network databases: in order to achieve high performance, ObjectStore does not by default keep enough information about objects to support fully general declarative queries. The programmer must understand the structure of the database in order to query it.
A final problem with object database management systems is that no standards have evolved in this world, either in data models, query languages, or programming languages. A user of ObjectStore, for example, is shackled to that product in a way that an SQL programmer will never be limited to a particular relational database. This is particularly distressing since no existing product or even research prototype provides a really complete set of capabilities.
While the preceding problems with ODMS are likely to keep traditional relational products selling for many years to come, it is hard to imagine a commercially-viable system along the lines of SITE CONTROLLER that is not based on some kind of ODMS.
-- Stewart Harrol
Version management in CAE systems is a research problem. In supporting civil engineers, one must keep track of who modified what and when in the design, ensure that derived data is marked invalid when the generating data is modified, and try to ensure that designers are kept out of each other's way. When the task evolves into supporting construction, the goal is that the state of the site at all times should be recoverable from a database.
The common substrates that are required here are the ability to track object evolution and to aggregate objects into consistent versions. Version management has been tackled by the design automation community since the early 1980's, for electrical engineering [Bhateja and Katz 1987]. The general approach is to add records to the database that describe aggregations of objects, or IS-A-PART-OF relationships, and the evolutionary history of objects, or IS-A-KIND-OF relationships. In addition, these systems support automatically supplying the latest stable version of an object to most of the designers, while allowing one or two designers to continue working on a new version of that object. Facilities for checking-out and then checking-in objects are common, as are change propagation mechanisms.
Finally, it is often necessary to collect mutually consistent versions of objects in a database into a configuration. In a software development system, this would correspond to a release of a new version of the product. In a civil engineering system, a configuration might be one possible way to lay out a site given a radically changed road network.
No standard version model or management system has emerged, but some unifying work has been done [Katz 1990] and version management is a standard feature of at least six object-oriented database products [Kim and Chou 1988; Object Design 1992]. Given the practical realities of the large size of civil engineering projects and the litigious environment, it seems clear that a successful civil engineering design system must have substantial version management support.
It is worth remembering that the standard equation of a line, Click here for Picture , has an orientation. If we plug an arbitrary point Click here for Picture into the left side of this equation, a value of zero indicates the point is on Click here for Picture , a negative value means Click here for Picture is to the right of Click here for Picture , and a positive value means Click here for Picture is to the left of Click here for Picture . We can get the same line oriented in the opposite direction simply by multiplying the equation through by a negative constant.
Figure 7.1 Oriented lines arranged around the edges of a triangle. Points to the right of all three lines are inside the triangle.
If we build appropriately oriented lines collinear with the edges of a triangle, we can determine query point (Click here for Picture ) inclusion by plugging the point's coordinates, Click here for Picture , into all three line equations. If the results all have the same sign, then Click here for Picture is in the triangle (see Figure 7.1). Consider the computation being performed here: Click here for Picture . If, for example, the summands Click here for Picture and Click here for Picture are large, then the contribution of Click here for Picture may be nil if it is combined with Click here for Picture first. I struggled with what I thought was a subtle bug in a geometry algorithm for several hours. I finally zeroed in on a triangle that was reporting Click here for Picture as outside of the triangle even though zooming in revealed Click here for Picture to be just barely inside. When Jim Little heard about this, he sagely noted that "Inner product accumulation frequently requires double precision arithmetic."
About 10% of my time working on the core of SITE CONTROLLER was devoted to hunting down bugs created by my unjustified faith in floating point numbers and then searching for alternative algorithms. Faster machines and floating point implementations with more precision simply postpone the day of reckoning. Exact arithmetic, i.e., rational numbers, is the only long-term solution that will give anyone confidence in complex geometric computation systems.
However, the 1980's brought two simultaneous revolutions: 1) the dumping on the market of thousands of people with bachelor's degrees in computer science, and 2) a collapse in the price of computer power. By 1990, the world looked very different from what anyone imagined in 1970. A corporation might still spend $500,000 for a mainframe but the programmers only cost $15/hour in 1970 dollars (i.e., after adjusting for inflation). Mostly, however, companies buy inexpensive prepackaged software on inexpensive personal computers and don't hire programmers at all.
Occasionally programming is unavoidable, either for a custom solution or because a company wishes to sell prepackaged software. Conventional wisdom today calls for a large group of low-paid programmers using 1960's-style tools such as UNIX, MS/DOS, and C. Any competent computer scientist could prove that this approach simply cannot work, yet at first glance it appears to and has produced billions of dollars in profits for many corporations.
There are a variety of reasons for the success of the "horde of C hackers" approach. One of the most important is that programmers today are solving problems that were first solved many years ago. For example, UNIX was developed in the 1970's with a subset of features of 1960's operating systems, most notably MULTICS; Microsoft Word was an incremental improvement of MacWrite, which was in turn inspired by work done at Xerox PARC in the 1970's; PC networks are reimplementations of systems that were developed on mainframes in the 1960's and 1970's; most database systems are rehashed versions of old IBM products.
The copy of a beautiful thing is always an ugly thing. It is an act of cowardice in admiration of an act of energy. -- Rémy de Gourmont. (This is my favorite description of C++.)
When one has a concrete idea of what the completed system should do, one is seldom forced to risk introducing bugs by modifying structures.
Another reason the "horde of C hackers" approach has worked remarkably well is that, although the resultant software is rife with bugs, most users have no experience with anything better. When an MBA's Macintosh Quadra crashes due to a C programmer's error in Microsoft Excel, he doesn't say "I remember back in 1978 that my VAX 11/780, with only one tenth the processing power of this machine, had memory protection between processes so that a bug in one program couldn't corrupt the operating system or other applications." Rather, he is likely to say, "Well, it is still easier than using pencil and paper."
Finally, big C programming projects succeed because they simply aren't that big. The biggest, most ambitious programs of the 1970's would still be big, ambitious programs today. For example, MACSYMA, a circa 1970 Lisp program, is still the world's most powerful computer algebra system, despite the hundreds of man-years and massively powerful new computers that have gone into making competitive C programs. Significant computer power was not widely available in 1970, so only a tiny number of people remember using really big programs two decades ago and therefore users believe today's programs to be remarkably big and ambitious.
Computer-aided civil engineering is different. Because the Global Positioning System is new and because sufficiently powerful computers are only now cheap enough for civil engineers, there are no mainframe or minicomputer systems that can serve as models for what PC software should do. For example, nobody knows a good way to capture a construction plan from a user. Any program that is thrown out into the real world is likely to be thrown right back with hundreds of deficiencies noted. If adding features to address those deficiencies introduces bugs, another important difference of civil engineering is going to make itself apparent.
Users may not be so forgiving of bugs in systems whose errors can cause the loss of millions of dollars or even human lives. Rebooting a PC because the word processor or spreadsheet crashed the machine is an annoyance. Bugs in complex computer-aided VLSI design systems may delay a integrated circuit's introduction to market, but would be unlikely to cost as much as the $1 billion lost in the Chicago flood. Anyone roasted in a Ford Pinto would probably argue that mechanical engineering errors can be just as deadly as civil engineering errors, but mechanical systems may be tested exhaustively before an investment is made in mass-production and dramatic failures are consequently rare. [In the case of the Pinto, the problem had been noted and debated within the company well before anyone was incinerated--that the company continued to use the design for reasons of cost was a failure of management, not of engineering.] By contrast, civil works are normally one-of-a-kind and realistic tests are often impossible. Thus, the Tacoma Narrows suspension bridge blows down, costing tens of millions of dollars, and the Kansas City Hyatt bridge collapses, killing scores of people.
Finally, computer-aided civil engineering is going to require enormous systems, much larger than the "mostly working" C programs currently being developed, with the added kicker that they must operate in real time. A system incapable of real-time response and error-free operation will be relegated to supporting civil engineering design only, a tiny portion of the industry. Construction is where the dollars are; models must be comprehensive and queried and updated in real time.
The problems seen by developers of the 1960's and 1970's most ambitious software systems have never been solved and they will come back to haunt developers of computer-aided civil engineering systems in the 1990's. Obvious problems include the following: 1) inherent complexity, 2) inherent dynamism of data structures, 3) maintaining extensibility so that unenvisioned capabilities may be added, and 4) maintaining high performance despite massive amounts of data and complex geometric problems.
An army of C hackers will not be able to surmount these problems. They will spend most of their time stepping on each other's toes, fighting their storage allocation bugs, ripping apart the system to add new features, and digging out from under the sluggishness of their ad hoc memory management algorithms. SITE CONTROLLER shows that a small group of programmers, working with good tools such as automatic storage management, a modern object system, higher-order procedures, metalinguistic abstraction, exact arithmetic, and a concise language, has a chance of overcoming the management-of-complexity and extensibility problems inherent in this area.
Bug-ridden programs make their mistakes instantly, quietly, and secretly. Tools that allow programmers to watch execution proceed at a human pace animate algorithms. The crudest form of algorithm animation is the stepper. Stepping through a program, a programmer gets to see each piece of code before it executes, complete with the values of local variables and arguments. Only after the programmer takes a positive action, such as typing a character, does the code actually execute. Since a typical computer can execute 10 million instructions per second and a typical human can type no more than 500 characters per second, this process slows down the program by a factor of at least 20,000 and is therefore impractical unless the programmer already has the problem narrowed down to a fragment of a big system. Thus, it was only on occasion that I was only able to gain insight into bug-plagued portions of SITE CONTROLLER by using the Lisp Machine stepper.
Algorithm animation is an active research area, spurred to some extent by frustration with the fact that the programmer has gained almost nothing from the hardware revolution that gave every computer user a big screen filled with windows and graphics. Even powerful, multiwindow programming environments such as the MIT Lisp Machine, Smalltalk [Goldberg and Robson 1983], and Cedar [Teitelman 1984], basically use graphics workstations as multiple ASCII terminals. If only those windows could be filled with different simultaneously-updated graphical views of an algorithm in action, the programmer could debug, the student might learn, and the customer would be impressed.
Deciding what information to present and at what stage in an algorithm's execution to update that information requires positive action on the part of the programmer. The programmer normally must also decide how information is to be presented, since standard programming environments provide no support for the graphical display of even fairly basic data structures, such as arrays, linked lists, and hash tables.
Consider a program that stores data in a hash table. An animation of this program might include the following:
* a window showing the source code with the currently executing line highlighted
* a window showing all the buckets of the hash table and their contents. If there are too many buckets, a view of the entire table shows a simple schematic drawing, perhaps with one pixel turned on for each entry in a bucket. However, zooming in would reveal detail and the bucket contents would be more fully described.
* windows showing input and output data marching along with program execution
* meters showing information derived from the program's data structures and execution, such as hashing efficiency and average access time
By watching this animation, a programmer would instantly be alerted to a bad hashing algorithm (clumps of data would collect in just a few buckets). If the clustering problem were related to the input data, that would be visible as well.
Geometric algorithms lend themselves to animation in more obvious ways. A plane-sweep Delaunay triangulation algorithm comes to life as the edges between points are drawn as the algorithm builds the final data structure [Gillett 1988]. Any algorithm that walks through a geometric data structure should be able to successively highlight each edge and vertex considered and give the programmer a printed report on what conclusions are being made. All the geometric algorithms in SITE CONTROLLER are implemented with some self-animation capability. This is because I discovered quite early that such programs invariably either work perfectly the first time or are impossible to debug without periodic graphical snapshots of their state. If a program works, the animation capability will be useful in training programmers new to the project. If a program fails, the animation capability will make debugging painless. Depending on the programming language, there are numerous convenient ways of ensuring that the animation hooks do not degrade performance or increase program size when not in use.
The 1990's will be a period of evolution for algorithm animation programming tools. Toolkits for animating standard data structures and interacting with arbitrary animations should evolve from academic experiments into standard commercial tools. A lucid overview of the topic and a description of Balsa-II, a pioneering system, are contained in [Brown 1988]. Tango, a spiritual descendant of Balsa that is less restrictive, is described concisely in [Stasko 1990].
The bottom line is that ad hoc algorithm animation saved me hundreds of hours in the development of SITE CONTROLLER; better and more complete algorithm animation should greatly facilitate the development of more complex successor systems.
Let's look back at the three components mentioned in Section 1: a central computer system such as SITE CONTROLLER; a location system; and on-vehicle computers. Recent advances in differential Global Positioning System receivers have made it abundantly clear that the precision required for earthmoving will be available soon in rugged, inexpensive packages. Research and development activities at machine vendors like Caterpillar indicate that the on-board computer and control systems required by SITE CONTROLLER can be designed and manufactured internally by any of the major American, European or Japanese manufacturers. My work on SITE CONTROLLER, study of the literature, and years of software development experience lead me to believe that a few dozen good programmers, supported by the best current tools, would be able to deliver practical, reliable software for every part of an integrated computer-aided earthmoving system.
Cutting the cost of earthworks by half is an entirely reasonable goal. Cutting the cost of hazardous waste site remediation by a factor of ten is probably an essential goal. Such dramatic cost reductions would change the shape of the planet and have an immediate effect on the lives of billions. All for the price of a few lines of code.
