Ken Robinson and Mark Martin (Rutherford Appleton Laboratory), Max Mehl (Fraunhofer Computer Graphics Research Institute), Allan Davison, Kieron Drake, and Mel Slater (Queen Mary and Westfield College)
To compete with popular US workstations, two European projects - EWS and Spirit - aim to produce the next generation of multiprocessor, high-performance, extensible workstations.
The European Commission funds a wide range of projects under its European Strategic Programme for Research in Information Technology (ESPRIT). Two of the projects funded under this Program are for the development of powerful technical workstations - the Euroworkstation (EWS) and Spirit. Both projects aim to provide multiprocessor, high-performance, extensible workstations for the 1990s.
These projects aim at providing European suppliers with the capability of supplying equipment that can compete with US products currently dominating the market, such as Stardent and Silicon Graphics workstations. Researchers intend EWS and Spirit to perform the tasks of technical and scientific professionals: visualization of complex data, image analysis, complex simulation, and photorealistic rendering of 3D scenes, either static or dynamic. These two projects also aim to satisfy various levels of graphics performance: flight simulators that render scenes at interactive rates, various forms of animation, and high-quality, static scene rendering.
|
Table 1: EWS partners and responsibilities |
||
|---|---|---|
|
Basic workstation, FPA, and optical disc |
||
| Gipsi SA | St Quentin en Yvelines | France |
| Bull SA | Paris | France |
| INRIA | Rocquencourt | France |
| INESC | Lisbon | Portugal |
|
Lisp coprocessor (Colibri) |
||
| Siemens AG (Prime Contractor) |
Munich | West Germany |
|
Electronic simulator accelerator (Esimac) |
||
| Siemens AG | Munich | West Germany |
| Brunel University | Uxbridge | UK |
|
Graphics accelerator engine (Grace) |
||
| FhG - AGD | Darmstadt | West Germany |
| Siemens AG | Munich | West Germany |
| Rutherford Appleton Laboratory | Didcot | UK |
|
Coprocessor communication system (CCS) |
||
| Chorus Systems | St Quentin en Yvelines | France |
|
SQL |
||
| Grupo APD | Barcelona | Spain |
The EWS hardware architecture is open and modular. Developers provide this modularity at three different levels: shared memory, a system bus, and a local area network. In addition to the basic CPU resource, a set of coprocessor boards provides specialized resources. The main components of the system follow:
Figure 1 shows a schematic of the overall architecture. There are other developments in the project, not described here. Table 1 lists partners collaborating on the project.
The BWS uses RISC technology to achieve state of the art performance, but aims to isolate the system from the particular chip set as far as possible. Researchers are initially using the Sun Microsystems Spare (Scalable Processor Architecture) chip. Each of the coprocessor boards is built on a standard general-purpose processor board (GPPB) that provides a hardware and software kernel and gives a standard connection mechanism via CCS both to the specialist hardware on the board and to the other EWS coprocessors. Currently the GPPB uses an Intel 80386 processor and has 32 megabytes of local RAM; upgrade to the 486 is straightforward. CCS itself is a message-based distributed operating system whose major facilities include real-time scheduling, virtual memory management, system integration of hardware, and an interprocess communication (IPC) facility, as Rozier (1) described.
The Spirit workstation hardware is based on the following concepts (see Figure 2):
Researchers designed Spirit's multiprocessor modular architecture to provide various levels of performance, in terms of computing power and graphics hardware capabilities, at a reasonable cost. Typical configurations range from 50 to 1,000 million instructions per second and 10 to 200 million floating point operations per second, with a very high performance graphics capability. The workstation will support emerging standards, including Unix and X11. In each case, the hardware will take maximum advantage of its multiprocessor nature while preserving the defined interfaces.
The Spirit architecture supports a set of (possibly heterogeneous) general-purpose processors that are under the control of the operating system and can execute any client program or process. In addition, the concept of dedicated engines as specialized coprocessors is fundamental to the system architecture. These dedicated engines will have architectures designed to support specific tasks. Examples of such engines under construction within the project are graphics and AI processors.
The operating system mentioned in the previous paragraph is a multiprocessor version of the Unix system. It supports threads (lightweight processes) and provides an appropriate interface to the dedicated engines.
A fundamental goal of the graphics subsystem is to be capable of real-time animation and interaction with 3D scenes at reasonable rendering quality. The subsystem must also support a number of application areas ranging from medical imaging at one end of the spectrum to real-time simulation at the other. Other goals include the following:
Table 2 contains a list of the partners on the project.
|
Table 2: Spirit partners and responsibilities |
||
|---|---|---|
|
Multiprocessor workstation and low-cost graphics controller |
||
| Kontron AG (Prime Contractor) |
Eching | West Germany |
|
Graphics hardware and associated software |
||
| Caption | Rennes | France |
| University of Tubingen | Tubingen | FDR |
| University of Sussex | Brighton | UK |
|
Graphics software architecture |
||
| Queen Mary and Westfield College | London | UK |
|
Multiprocessor Unix, languages, and overall systems issues |
||
| Acc | Amsterdam | The Netherlands |
|
AI processor |
||
| Bae | UK | |
The graphics hardware in high-performance workstations needs to support high-speed geometry calculations, rendering, windowing, and frame-buffer management. Developing special purpose hardware must always balance algorithm needs and the capabilities of specific hardware solutions. In general-purpose workstation design, no single solution provides a panacea for all applications or algorithms.
We see basically two approaches to graphics support. Some supercomputer workstations (Stardent, Apollo DN10000) use increasing multiprocessor performance as a pool for common graphics enhancements. Thus, graphics benefits as do all applications. Pixel-oriented parallelization of the frame buffer access dominates the specialized graphics enhancements in this approach. This approach has advantages in porting software and ease of exploiting technology trends. The drawback is that graphics requirements compete with applications for the same processor resource.
The alternative approach (as exemplified in the Silicon Graphics Iris GTX and Sun TAAC-1 accelerator) is to construct a parallel and pipeline system of highly specialized components exclusively for graphics support. New generations of hardware require the adaptation of many graphics libraries, which have to be provided by the workstation supplier. To ease porting of new graphics software, the graphics hardware must be designed carefully, bearing in mind that use in a general-purpose programming environment is the goal. Thus there is a need for flexible programming support, using graphics standards as basic interfacing methods, to integrate video sources into a window environment, provide user interface tools tailorable to application demands, and optimize high-speed hardware.
The Grace developments within EWS will overcome both the overloading of the basic application processor(s) with graphics support and restriction of the specialized graphics coprocessor to manufacturer-supplied functionality. This will be achieved by a programmable microprocessor system that supports graphics standards such as X, PEX, and PHIGS+ by a combination of general- and special-purpose processors.
For the longer term, the integration of video with computer graphics is becoming more important for research, development, and presentation. This connection is a nontrivial task, however, because of different standards for resolution, scan rate, and color implementation of the specific media, as the high data rate exceeds the capacities of today's standard I/O hardware. Some commercially available workstations do offer boards for live video integration, but only under various restrictions. Some use a low-resolution video window on a high-resolution screen, while others block out the rest of the display while the video is running. Another solution offered is to generate video output by using the interactive tools of the primary display. This provides high-resolution video, but does not effectively support high-speed graphics. Use and manipulation of video must be a fully integrated feature and a viable tool in the computer graphics environment.
Researchers now developing the current development of the graphics coprocessor engine (Grace) are focusing on the following:
Analysis of these requirements shows that graphics subsystems for the 1990s will have to attain the following goals:
Earlier we discussed the alternatives of a processor pool versus highly specialized graphics hardware. The Spirit graphics subsystem has a set of processors dedicated to graphics. However, the architecture is hybrid, providing a pool of general-purpose (reprogrammable) processors dedicated to graphics but without the disadvantages associated with either of the approaches mentioned earlier. This does not require the sharing of graphics processors with competing applications, nor are the graphics algorithms embedded in hardware.
Workstation graphics hardware in the early 1980s focused on the provision of support for the novel direct manipulation user interfaces that developed as a result of Xerox Palo Alto Research Center work in the 1970s. As the decade progressed, more and more hardware manufacturers produced specialized 3D graphics boards. These provided support for fast 3D vector and polygon rendering. They also solved the hidden surface problem with a z-buffer and based illumination models on Gouraud and Phong's early work - all relatively simple to implement in hardware terms. In other words (and not unnaturally), by the end of the 1980s standard graphics hardware had implemented the results of the research of the 1970s. It is likely that the same will happen in the 1990s in relation to graphics research of the 1980s.
In the 1980s attention focused on photorealism, through ray tracing and radiosity paradigms. The end of the 1980s saw an explosion of interest in virtual-world environments, where users have the illusion of being in and interacting with an entire 3D world. In addition, attention focused on bringing physics and mechanics into the graphics equation, with the introduction of locally deformable object models and models that support objects that are active in the sense that they respond appropriately to forces in their environment (for example, by bending, stretching, twisting, and other deformations). See Terzopoulos and Fletcher (2)).
A workstation under development in the early 1990s must take into account such futuristic developments if it is to survive in the marketplace. Of course, future hardware must also support the usual 1980s style of graphics hardware capabilities. The hardware and software architectures must, however, be flexible enough to allow the introduction of new algorithms and approaches in the future, without the necessity of developing an entirely new architecture. The modular and flexible Spirit architecture aims to provide a certain level of guarantee for the future in this respect.
The graphics subsystem supports the following key requirements:
Following the arguments about trends above, the graphics subsystem is designed to be extensible and modifiable. Application programmers achieve this through a behavior mechanism (discussed more fully later).
These same requirements follow from considerations about developments of standards. At present the standard interfaces include X11 and PHIGS+(PEX), and obviously every workstation must support these. In the 1990s, new standards will evolve. We'll need flexibility at both the hardware and software levels to allow for such changes, or architectures will rapidly become obsolete.
Obviously, what this type of system needs is a powerful, extensible environment for the development and execution of software for high-quality visualization. This environment should support current standard systems such as PHIGS and the X Windows system as well as future developments in the field. Equally important, the system must supply a number of features to provide a good user interface and a powerful programming environment. The system can meet some of the goals of quality user interaction in this type of environment by providing the tools for an effective style of working, as in Schneiderman's direct manipulation paradigm (3). In particular, users require tight coupling between input device (such as mouse) movements and visual feedback, so they can fully exploit their motor skills. Overall, the system should provide quality by good response and user control of the session as well as by sheer graphics functionality and performance. In addition, it should provide support for a wide range of I/O media to permit effective exploitation of the system resources. Although the mouse is an excellent all-around input device, its use in three dimensions is unintuitive. The system should therefore be able to support a range of input devices, with the aim of moving their use from research to end user.
As for human factors, we have learned many lessons in human-computer interaction, but we haven't applied them. For example, we understand the need for double buffering of graphics images, but we only rarely apply them to many user interaction processes, such as dragging graphics images on the screen. As a result, many systems are visually distracting and even uncomfortable to use. Retained windows, which keep a copy of obscured parts of windows in off-screen memory, allow freedom of window movement at low cost. Thus, applications don't need to have complicated code to repaint portions of windows. We also need to apply what we've learned about cursor images. These are often the natural focus of the user's attention, thus we can use them to carry much more information than is normally provided.
EWS attempts to achieve these goals for graphics software environments by supplying an object-oriented interaction framework (IF) that provides a dedicated architecture to support user interaction. This framework must support a diverse set of applications, graceful cooperation with existing and future trends in interactive techniques, and the development of standards in windowing and graphics.
Figure 3 shows the structure of the IF and its relations to the other EWS components. This architecture exploits the development of the X Window system and hence provides a ready path for existing applications to be ported to EWS. It also tackles the major drawbacks and limitations of the X system in the graphics workstation context. For example, the overheads involved in X with passing user input to the application and back to the display for feedback/output are significant; in fact, they militate against very high quality. A later version of the IF will thus contain an object store, which allows application-dependent objects to be downloaded into the Grace board for fast feedback to user input. (Researchers designed the rest of the IF with this requirement in mind.)
Furthermore, X's designers made it essentially a 2D interface, with consequent restrictions on its applicability. In the EWS context, however, a mechanism exists for extending the X protocol and the X server to handle non-2D applications. Finally, the standard X server as supplied by MIT has only a single thread of execution, thus it is possible for a single process to hog the interaction resource, leading to unacceptable response with other applications executing. Some researchers discussed multi-threaded X server development (4), which will be addressed in a later stage of the EWS project. (The CCS operating system has features that enable the user to tackle this problem.)
In addition to the above limits within X, there are always firm limits on what hardware can provide. The software should endeavor not to make these limits explicit to the programmer, but to provide a graceful degradation when they are reached and simulate unlimited resources. For example, the display will have a fixed number of hardware-identifiable windows. The system will label each pixel according to the number of the window it is in, allowing efficient handling of windows of arbitrary shape (recently introduced in Release 4 of X11). However, X was designed with the concept that windows are cheap resources, so some applications will allocate many windows within a parent window, one per interaction atom. We might quite feasibly run out of hardware windows. The design of the IF therefore allows the hardware to implement the windows, or the software will simulate them if the hardware resource is exhausted. This is done by extending the X server capabilities.
Since most applications will be based on the BWS and will in the first instance use the X server on the Grace board, the system needs to transport data between the two CPUs. CCS provides the basic transport mechanism to do this over the system bus, and the X Windows protocol used between the X library and X server provides the higher protocol needed.
We can exploit some significant features of the CCS system to help construct the IF. CCS supplies a Unix interface with such non-Unix items as the ability to create multiple threads in a process (actor) and to run at real-time priorities. Separate threads can be used to provide effective user feedback while some autonomous time-dependent action (such as a picture of a rotating globe) is in progress; alternatives require complex software solutions. In addition, some aspects of managing the display must take precedence over others for effective feedback, and the CCS real-time priorities are relevant here. To illustrate this, consider a window being dragged across the display. Other windows might start repainting newly visible areas, but this should not be allowed to interfere with the tight connection necessary between mouse movement and cursor or window position. Also, there might be little point in repainting an area whose contents are changing in any case.
The connection to the graphics pipeline carries the rendering requests (see below) and must also transfer large amounts of data (both ways in the case of images). The pipeline protocol includes the following:
Researchers designed the interface to the graphics hardware to support a wide range of current and future standards. Researchers also considered the requirements of standards such as PHIGS and proprietary software such as Renderman and Dore.
For performance we need to batch frequently used requests together, hence reducing setup time by sharing it across many similar operations. Further, several consecutive operations might have many arguments in common, such as color, window, font, and so on. These arguments can be collected together into a graphics context that needs to be sent only once for the operations using it. To improve data throughput, several independent graphics contexts can be held by the graphics pipeline.
The pipeline nature of the graphics rendering hardware causes some problems when paint and raster operations are juxtaposed. The system needs a synchronization mechanism to ensure that pixels are not addressed too early, before a previous paint operation has completed. To maximize use of the rendering hardware, the server can avoid this wait for synchronization where it is recognized. The server can fill in time waiting for a paint operation in one window to be guaranteed complete by painting another window. This could be followed immediately by a raster operation in the first window with no synchronization delay.
The system supplies programmer's tools as an object library, which provides an extensible programmer interface written in C++. We can see the class hierarchy as supporting applications in three domains: support for high-quality modeling and rendering through the 3D classes, ameliorating the construction of user interfaces with the interaction classes, and providing application integration and fine-grained control with the process classes.
The elegant and compact interface specification offered by Renderman (5) influenced the 3D classes. The application developer need not be concerned with the low-level detail of the 3D extensions to Xlib, as these are hidden by the implementation of the class hierarchy. The abstract superclass primitive surface provides the support for a comprehensive set of geometric primitives, including quadric surfaces, bicubic patches (including the ability to specify an arbitrary basis matrix), and non uniform rational B-spline surfaces. A synthetic camera determines the appearance of a rendered scene. The system can direct multiple cameras on a single scene, the cameras being able to move around the scene independently.
The Graphics Environment class maintains the current graphics state and provides a means of assigning values to the attributes of the various geometric primitives. A Graphics Environment is represented for each Window displayed on the screen (the Window class itself is described shortly). To heighten the realism of the rendered models, the system makes both texture and bump maps available. Greater realism could be afforded by implementing a facility similar to the shading language found in Renderman. The shading language itself is based on Cook's shade trees (6) and allows fine control over the material characteristics of a surface. Further classes include Light Source, Color, and Shader. The light sources supported are ambient, distant, point, and spotlight. The shading interpolation offered by the Shader include constant shading, Phong, Gouraud, and cheap Phong.
For rapid prototyping of user interfaces, researchers developed a framework to allow construction of the interface using direct manipulation. The design attempts to offer similar capabilities to that of the interface builder featured in the Next machine's Next Step environment. The constructor set to be made available in EWS will connect the interface items found in the interaction classes, as well as custom objects. Developers adopted the Model View Controller paradigm (7) of Smalltalk-80 to construct the object dependencies required to effect the messaging between objects when the interface item is notified of its respective user events. The abstract superclasses, Window and Action, describe the view of a model and how the user might interact with it. Examples of classes that reuse Window include the Button, a Preferences class that supports connected interface items, and the Slider.
The features of the CCS system, including IPC and lightweight processes in the form of spawned threads within a parent actor, provide the abstractions for building powerful process-oriented classes. The process classes developed to date go beyond the protocol offered by Smalltalk-80's classes for supporting multiple independent processes and have been fashioned after the C Threads package written for the Mach multiprocessor operating system (8).
While the initial implementation will of necessity be somewhat sparse because of effort and time restrictions, researchers took care to ensure that hooks are present for a realistically full set of classes.
Spirit researchers based their software architecture on a uniform software component called the graphics interface layer (GIL). This provides the basic functionality to support systems such as X11 and PHIGS+ across the range of possible hardware configurations. It is also simple and versatile enough to be used directly by applications that do not wish to use standards such as X11 or PHIGS+. It provides a device-independent interface to the range of different hardware options available. From the viewpoint of a systems software generator, the GIL is a standard interface layer to the graphics hardware. From the viewpoint of an applications programmer, the GIL might be seen as a graphics library.
The GIL is based on a small number of concepts, represented in an object-oriented style. For example, consider the concept called Shape. Shapes are created as instances of a Shape class, and methods are provided to create and otherwise manipulate such Shapes. The interface language is initially C, but the system will also provide interfaces in a number of other languages.
As summarized in Figure 4, the GIL itself has a number of conceptual layers and features:
The GIL 2D level is the basic layer that a client can use to construct windows, graphical output, and input. The main concepts in this layer are Shapes, Regions, Attributes, Color Lookup Tables, and Events. Being at a more basic level, the GIL does not itself provide a window system. Instead, it provides only the mechanisms on top of which a client can build a number of different window systems. This layer is the point at which the X server would be ported to the Spirit workstation.
The GIL 2D layer includes Shapes that describe (in the first implementation) sets of rectangles. A later implementation will extend this to arbitrary geometric paths. Regions have a Shape and a content (that is, color values). Regions might be allocated hierarchically from the frame buffer, or from off-screen memory. They have associated attributes such as color lookup tables, and Regions can be combined by a method that is a generalization of the usual raster operation function. The output functions include all of the obvious ones, such as setting pixels, lines, polygons and curves (Nonuniform rational B-splines). The system associates an Attribute object with a graphical output primitive at the time of invocation of the output function. Attributes include combination rule, color, clip shape, and antialiasing quality. The 3D layer provides basic 3D viewing and rendering. Researchers based it on the concept of a View, which has associated Camera and Illumination models. A View is associated with a Region, which acts as the connection between the 3D layer and 2D graphical I/O. Of course, at any one time, there can be multiple views. The system constructs Windows on top of Regions, so that it can construct a Window system based on 3D graphics. The camera model is based on the standard CORE concepts (adopted also in the Graphical Kernel System (GKS) for 3D and PHIGS) including such concepts as View Plane Normal, View Up Vector, and so on. However, the system provides a general mechanism to allow the definition of other camera models. The Illumination Model represents ambient light and a set of (point) light sources, each of which can be arbitrarily positioned, colored, turned on or off, and so on. The output primitives again include all of the usual ones, such as vectors, polygons, and NURBS. The output primitives also provide antialiasing quality and texture mapping on a primitive-by-primitive basis and also as attributes of the View.
The structure interface layer (STIL) of the GIL provides an interface for the construction of a generic graphical object hierarchy for graphical modeling. The PHIGS structure network is an instance of the STIL, but not the only possibility. This level thus provides mechanisms for the creation of graphical objects as nodes of an acyclic graph - that is, an object is created as a child of a parent object that might be the root node or a descendant of the root. Modeling transform matrices instantiate the geometric relationships between parent and child objects. Mechanisms exist that traverse the tree and convert the modeling coordinate systems (conceptually) to world coordinate space, then render the constructed output primitives. The system can also port implementations of PHIGS to the workstation at this layer.
The input layer supports an event-based input mechanism and will support multiple event queues per client, synchronous notification of events, arbitrary (user-generated) event types, event filtering (using an interest mechanism similar to News), exclusive or shared access, and prioritized event distribution. In association with the process mechanisms supplied by the operating system, the input layer can also synthesize asynchronous event handling for those systems that need it. Researchers designed the input system (as a future enhancement) to be extensible toward distributed input systems by mechanisms similar to the Linda tuple space. Input ranges from the simplest, such as the (2D) position of a pointing device, to the most complex detection of an object in 3D space.
In general the GIL does not aim to support directly the plethora of events required by, say, X11. In any case it is impossible for the GIL to know which regions correspond to X11 windows and which do not. Rather, the GIL aims to provide an event distribution and access mechanism. Device drivers and other processes can use it to post events, and clients (such as the keyboard and mouse handlers in the device dependent layer of X11-DDX) can use it to read events. Thus the GIL itself never generates any events at all: it merely provides access to the various input devices so that device drivers able to create and post the required events can be written.
In fact, a standard driver will be provided as part of the standard GIL interface, but this is at a higher level than the basic GIL specification needs to include. This flexibility is crucial since it allows a client to use raw GIL for output and have the X11 input handler as well, or vice versa, or many other combinations. Thus, the GIL input layer provides mechanism but not policy.
A so-called Behavior mechanism is provided by the GIL to overcome problems associated with different language binding interfaces to the GIL, and more importantly to provide extensibility. This is a language that will allow clients to select between several different predefined behaviors of parts of the system - for example, different methods of illumination (Phong rather than Gouraud) or texture mapping. Also, it will allow clients to define completely new behaviors (such as a new method of illumination) and execute them on the appropriate processors. In particular, the Behavior mechanism allows loading into the graphics system of a new set of functions that change the behavior of the STIL - such as adding different output primitives or a different method of traversal of the object hierarchy. This language provides a means for a client to reprogram the behavior of the system - which was one of the requirements for flexibility discussed earlier. The language also allows clients to specify and install their own error handlers for when various classes of graphics exceptions occur.
Programmers using the graphics subsystem will have the ability to program directly using the GIL interface library. Moreover, the Behavior mechanism will provide a powerful extensibility mechanism to allow the incorporation of novel algorithms and techniques. Obviously, the graphics standards such as GKS and PHIGS+ are supported - indeed, a very fast implementation of PHIGS+ is an important objective. The graphics subsystem is clearly intended to provide an easy porting environment for graphics standards, and also the important distributed windowing standards. We summarize the relationship between GIL, graphics, and window standards in Figure 5. (Here no distinction is made between the 3D level and the STIL - this is in any case only a conceptual distinction.) Note that all levels of the GIL have direct access to the graphics hardware. The system allows porting of purely 2D systems such as GKS(2D) and Postscript directly on top of the 2D level. X11 is ported partly on top of the 2D and partly on top of the 3D levels (to support PEX). Applications can use any level of the GIL directly.
While the Spirit workstation supports standards, research continues on systems for the future. At Queen Mary and Westfield College researchers have a particular interest in the virtual worlds model for interactive systems, where the user model is based on a 3D world rather than the usual Flatland picture presented on all of today's interactive interfaces. For example, when starting up the computer, users might be placed in an environment not unlike their own office (this might, of course, have several disadvantages as well as advantages). The system might request navigation of a computer network as moving through a set of corridors in a building, and so on. There are, of course, real 3D (CAD) applications that require precisely this type of interface.
Corresponding with this, research continues on a 3D paradigm suitable for the modeling, description, and display of scenes. The search here is for a simple model, much as the stencils model provided a successful underpinning for Postscript. This 3D paradigm will be the heart of a 3D description language, probably itself an aspect of the behavior language mentioned earlier. This research includes recent study into deformable models.
The Spirit workstation will provide an object-oriented software development environment, specifically Smalltalk-80. This provides a number of key features that will be exploited and improved upon for Spirit.
Smalltalk-80 supports software reuse with a class-based single inheritance scheme. Spirit's Smalltalk-80 (Spirit ST-80) will provide an implementation of class-based multiple inheritance supported at the virtual machine (VM) level. Researchers will also investigate reuse based upon prototyping and delegation. Spirit ST-80 will extend Smalltalk-80's interleaved multiple processes with a truly concurrent multi-processing model that will exploit as many processors as are available. The VM will be replicated on each available processor with access to Smalltalk objects in shared memory.
Queen Mary and Westfield College has built a prototype VM that uses dynamic translation. This will form the basis of Spirit ST-80's VM. To improve performance in a shared memory configuration, the prototype VM keeps activation state in local memory, only converting this into object form when necessary. Further, Smalltalk code, represented by compiled method objects, is not executed directly, but is converted into threaded code as required. The VM then executes this threaded code, which is cached in local memory. A Smalltalk VM accesses activation state (such as stack content) and code much more frequently than ordinary Smalltalk objects, so these two features should substantially reduce accesses to the shared memory. Research still needs to be done on appropriate garbage-collection techniques, as the current deferred reference counting system is likely to perform poorly in a shared memory configuration.
Researchers will build control for multi-processing by using the existing Smalltalk-80 Semaphore and Process objects and extending their associated primitives of signal, wait, resume, and suspend to work over multiple processors. Researchers will also change Smalltalk-80's debugger to support the debugging of multiple processes. Almost certainly Smalltalk-80's notion of process and process scheduling will not be rich enough for Spirit, and developers will need to make enhancements.
Spirit ST-80 will use the Spirit graphics system for its user interface, discarding the simple bitmap graphics of Smalltalk-80 in favor of the extended Postscript imaging model supported by the GIL.
The graphics co-processor Grace is built on the general-purpose processor board (GPPB) used for integrating the distributed operating system. This simplifies software portability and interfacing of special-purpose hardware, in this case the 3DGRP (3D geometry and rendering pipeline). The 3DGRP handles the geometric tasks (transformation, clipping, object subdivision) as well as high-speed rasterizing and shading by parallel frame buffer access. The system implements a distributed frame buffer design with five memory banks in parallel. (Figure 6 shows the architecture.) To allow window operations such as moving or deleting, the system supplies a display memory to support reconstruction of obscured windows. A high degree of window support by hardware will be available in addition to frame buffer management, and future enhancements will manage the integration of video sources into the window system.
The geometry and rendering stage considerations follow. Developers first introduced structuring geometry calculations into a pipeline approach as a chip design in the geometry engine (9). Researchers developed GKS chips for use in the Graphical Kernel System. The geometry stage performs the transformation process (modeling, viewing, perspective) and the clipping in 3D. Extensions of the geometry pipeline resulted when developers included high-quality raster-graphics algorithms. These form the full image generation pipeline with the stages performing the tasks of rendering (illumination, z-buffer hidden surface elimination, shading, scan conversion, and window management).
Many modern workstations (10) use this scheme of image generation. The hardware realization of such a simple pipeline structure has, of course, inherent system design difficulties. For a variety of algorithms, it is nearly impossible to obtain a well-balanced system using an inflexible hardware solution. The load in the transformation stage is linearly dependent on the number of control points describing the graphics objects. The load of the clipping stages are data dependent, but might be balanced simply by having FIFOs as intermediate storage elements. The issue becomes much more unpredictable if rendering is integrated into the image pipeline. The load in each stage depends on the display methods and algorithms used.
Researchers based the approach for the graphics architecture in EWS on a multi-processor subsystem with load-balancing capabilities between the geometry and the rendering stages. The rendering processors can also perform geometry operations. They have access to the data FIFOs and perform geometry calculations whenever no rendering tasks have to be done. Furthermore, the system can port existing software and produce the graphics libraries because it uses C-programmable microprocessors (Texas Instruments 320C30).
The frame buffer is closely connected to the rendering stage. Researchers designed it as a distributed frame buffer architecture that connects the columns of the frame buffer to different rendering processor units. Currently, there are five rendering units in parallel, and developers plan to expand to eight units to gain higher resolution. The design of an ASIC that functions as memory control and Gouraud shading unit for span interpolation supports the pixel generation into the frame buffer. In addition to access within the memory banks during image generation, a crossbar switch design handles the interbank accesses, such as for raster operations (bit block transfers).
The frame buffer consists of five column-interleaved memory banks, each one connected to a rendering processor. This allows parallel access of all processors to their memory bank without interfering with the others. The development of column-oriented filling algorithms is straightforward. The timing constraints of the video refresh determined this organization. The horizontal resolution of the screen (5 × 256 = 1,280) and the size of highly integrated virtual RAM govern the number of memory banks.
As shown in Figure 7, the frame buffer consists of three memory units. The number of bits per pixel given below is the maximum depth supported. Depending on space and cost requirements, researchers might configure lower level solutions:
As shown in Figure 7, during one refresh cycle out of the on-screen memory, the system can make a copy of all the visible pixels and store them in the display memory. This happens in parallel to the monitor refresh. The cross-bar switches in the video refresh path can be programmed to switch the sources of the display refresh to either on-screen or display memory. This allows reorganization of the on-screen memory contents (for example, out of the off-screen memory) without visible intermediate effects on the screen.
Additionally, during copying of the frame buffer contents, a group of windows, consisting of an arbitrary set of pixels, can be selected and moved by offset generation. This enables moving windows of any size, shape, and color depth within a small number of refresh cycles.
Further extension of the EWS graphics architecture will gain higher resolution by increased parallelism. The speed of pixel generation into the frame buffer depends on the optimal access methods (page mode) of the virtual RAMs. An enhanced shading controller ASIC makes this possible.
For integration of video sources, the connection of a video frame buffer to the crossbar switches parallel to the rendering units offers full integration into the workstation window environment. The next-generation prototype will include this design.
Spirit researchers based their graphics subsystem on three types of boards:
The LCGC forms the basic display system. It provides for up to 2K × 2K resolution with 8 bits per pixel, with a 7-Hz refresh rate. It has a specialized graphics processor to provide video control, basic 2D graphics output, and some support for cursors and text. Optionally, this board can have a 24-bit full-color frame buffer that can be overlaid on a pixel by pixel basis on the 8-bit frame buffer.
The object and image boards provide an (optional) graphics component called the high-performance graphics subsystem. Note that the graphics functionality of the Spirit workstation will be independent of the hardware configuration. Obviously, though, very high performance (for example, real-time animation) will require the high-performance hardware.
The system operates in parallel within the high-performance graphics subsystem by having more than one object and/or image board. Multiple image boards will achieve parallelism through division of the display, and multiple object boards will achieve parallelism through division of the geometric processing (for example, management and processing of a hierarchical object store). The multiple processors on the object and image boards provide a further degree of parallelism. Even with the LCGC option, the implementation of the GIL will take advantage of the multi-processor nature of the workstation itself to provide parallelism.
One of the major requirements of the object board is to support a hierarchical object store or structure network. Although similar to the lines of PHIGS, it is (crucially) not limited only to PHIGS objects and concepts because the object board is a programmable resource with the capability of supporting a number of systems. The main object board tasks follow:
The image board tasks include the following:
The image board is supported by a number of ASICs, such as the one needed for scan conversion.
The relationship between the GIL and the hardware components is as follows: The processor that is part of the LCGC will support the 2D graphical output and input as far as possible. The image board supports the rendering part of the 3D layer, while the object board supports the viewing and STIL components. In the case of a configuration that contains only the LCGC, the GIL implementation will be divided between the main processors and the LCGC. The functional specification of the GIL is the same for any hardware configuration.
For EWS, the basic BWS and FPA systems will obviously exploit the planned growth in RISC chip set speeds over the coming years, as will the GPPB. We also envisage a faster system bus. On the graphics front, we can expect the following advances from the EWS project:
Future enhancements of Spirit will focus on a number of areas including (but not exclusively):
Every design process involves trade-offs. In the graphics workstation area, the trade-offs are between modularity, performance, flexibility, and perceptions of future requirements. The EWS and Spirit teams have achieved significantly different designs and trade-offs from similar overall requirements.
Of necessity in projects of this type, teams carried out much of the work, not individual authors. There are too many individuals and organizations to acknowledge directly, and we hope that they will accept our heartfelt thanks for their efforts, which we report here.
The research is part of the ESPRIT II program funded by the European Economic Community. As with all ESPRIT projects, these are multi-national, multi-institute cooperative ventures, with half the funding provided by the participating organizations.
1. M. Rozier et al, The Chorus Distributed Operating System, Usenix Computing Journal, Vol. 1, No. 4, Sept. 1988, pp. 305-370.
2. D. Terzopoulos and K. Fleischer, Deformable Models, The Visual Computer, Vol. 4, No. 6, Dec. 1988, pp. 306-331.
3. B. Schneiderman, Designing the User Interface: Strategies for Effective Human-Computer Interaction, Addison-Wesley, New York, 1986.
4. I. Elliott, J. Brezak, and N. Myers, A Multi-threaded Server for X and PEX, Proc. of the X Conf., Boston, 1990.
5. S. Upstill, The Renderman Companion: A Programmer's Guide to Realistic Computer Graphics, Addison-Wesley, Reading, Mass., 1989.
6. R.L. Cook, Shade Trees, Computer Graphics, (Proc. Siggraph), Vol. 18, No. 3, July 1984, pp. 223-231.
7. G.E. Krasner and S.T. Pope, A Cookbook for Using the Model-View-Controller User Interface Paradigm in Smalltalk-80, J. Object-Oriented Programming, Vol. 1, No. 3, Aug./Sept. 1988, pp. 26-49.
8. E.C. Cooper and R.P. Draves, C Threads,, Tech. Report CMU-CS-88-154, School of Computer Science, Carnegie-Mellon University, Pittsburgh, Penn., 1988.
9. J.H. Dark, The Geometry Engine: A VLSI Geometry System for Graphics, Computer Graphics (Proc. Siggraph), Vol. 16, No. 3, July 1982, pp. 127-133.
10. K. Akeley, The Silicon Graphics 4D/240GTX Superworkstation, IEEE CG&A, Vol. 9, No. 4, July 1989, pp. 71-83.
Ken Robinson is the leader of the User Interface Design Group in Informatics Department at the Rutherford Appleton Laboratory. He has been involved with software and tools for highly interactive workstation environments since 1982. His group's research interests include advanced user interface design (UID), UID tools, remote cooperative working, novel input devices, and human factors. He has a degree in physics and a PhD in astrophysics, both from the University of Manchester.
Mark Martin is a researcher at CETIA in the south of France. He integrates live video with X11 graphics workstations and terminals. He has research interests in real-time and multimedia control and presentation. He received his BSc from the University of Newcastle, UK.
Max Mehl heads the graphics hardware development department at Fraunhofer Computer Graphics Research Group. He supervised the de sign of the graphics subsystem in Grace. His research interests are architectural, multiprocessor, and ASIC solutions for rendering tasks. He received his diploma hi computer science in 1982 from the Technical University in Darmstadt, Germany, where he is now working toward his PhD.
Allan Davison has been a lecturer at Queen Mary and Westfield College since 1980, where he teaches logic design and microprocessor systems at undergraduate and postgraduate levels. He is involved in research on computer architecture and graphics, including the design and construction of an X11 terminal based on transputers. Allan has a BSc in mathematics with computer science and an MSc in computer science, both from Queen Mary and Westfield.
Kieron Drake is technical leader of a project to develop the X11 testing and validation suite on behalf of MIT. From 1984 to 1990 he was a researcher and lecturer in the computer science department at Queen Mary and Westfield College. His research interests include interactive high quality computer graphics, computer architecture, object-oriented programming, user interface management systems, and window systems. He is a co-author of a forthcoming book on the X11 and News distributed window systems. He holds a BA and an MA from Cambridge University.
Mel Slater has been a lecturer at Queen Mary and Westfield College since 1981, where he teaches computer graphics. He has been involved in computer graphics research for several years, and in 1987 he co-authored a textbook entitled Computer Graphics: Systems and Concepts. He received his BSc and MSc in statistics from the London School of Economics.
