17Tanner.tioga
Rick Beach, February 15, 1987 8:10:09 pm PST
Multi-Thread Input
Peter P. Tanner
Computer Graphics Laboratory
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
(519) 888-4589
PPTanner%watCGL@Waterloo.edu
Abstract
Implementors of interactive computer workstations have tended to shy away from making several devices simultaneously available to a user of their systems. The principal reason for this reluctance has been the difficulty faced by an application program in analyzing the several streams of input that such a configuration would present. Recently systems have been developed that support such multi-thread input. This paper discusses the requirements of multi-thread input and gives examples of how the requirements are being met by the experimental systems.
Introduction to multi-thread input
Multi-device input is the presenting of several simultaneously active devices to the user, with which he may perform several concurrent activities. The user need not specify which device is to be used; he just uses it. The frequently used analogy between the user of an interactive workstation and an automobile driver serves to illustrate the multi-device input situation. When a driver wishes to brake, he does not make the brake pedal active by selecting a menu command, he simply applies the brakes. This direct relation between a physical object (the brake pedal) and the resulting action (the slowing down of the car) is ideal for the implementation of easily understood and easily used direct-manipulation capabilities.
As far back as the mid-70's, a multi-device input system was added to the GRIP-75 system at the University of North Carolina, a system for displaying electron density maps produced by X-ray crystallography [2]. The implementors found that their ``use of analog joysticks and knobs to express manipulations . . . made the largest single improvement in the ease of system use''. Their experience led them to believe that ``Similar systems [which] sometimes use the data tablet for all interactions and motions — [were] a little like driving a car with one hand tied behind your back'' [8]. This comment is still valid for today's mouse and keyboard interfaces. Full parallel input requires support for several streams of user input directed to a single application, where each stream:
 comes from a different input device (multi-device input).
 is processed in a manner that is lexically and syntactically separate from the other streams (multi-thread input).
 is logically asynchronous with respect to each other (requiring multi-tasking support).
vspace:2.1in:
Figure 1. Parallel input flow from devices to application
Figure 1 depicts an architecture that would support parallel input. The Switchboard (or Workstation Agent [7]) is responsible for routing the input streams from each device to the associated Dialogue Manager (DM). The fact that the DM's and the application modules are separate inter-communicating tasks ensures that the threads of input may be processed asynchronously.
Multi-device input includes the concept of several virtual devices based on a single physical device (such as the use of tablet or mouse windows), as long as several of these virtual devices are being used in a single application. However, such systems, if relying on a single input device in addition to the keyboard, do prevent the use of anything but single-handed input.
Justification of multi-thread dialogues
Computer workstations compare poorly, in terms of bandwidth of interaction, to such commonly used tools as an automobile or a sewing machine. Buxton decries this current state of workstation design by imagining future peoples' impressions of current beings after their discovery of a ``fully-stocked computer store from the 1980's'' [4]. Their image of our physical capabilities would be badly distorted to say the least. In another paper, Buxton and Myers describe an experiment that shows the value of two-handed input [3]. Even without such experimentation, our own experience driving cars, playing musical instruments, and paddling a canoe leads us to accept that the use of both hands and feet (and auditory feedback although this is not under discussion in the paper) deserves consideration in our workstation design. Some of the most successful computer workstations have been those dedicated to a very specific application that have made use of a set of input devices designed for that application.
Multiple input devices (physical and virtual) are a way to improve the communications path between user and computer, but one can only profit from their use if proper multi-thread input support is provided in the system's user interface management software.
Multi-thread support — current status
Primitive philosophies of input, apparent in both FORTRAN and UNIX, treat all input as files that are to be read. Once a second input device is added to a system, this model of input as files breaks down. If a device is read, the program is suspended until the user has done whatever needs to be done to the device to convince the device handler that it has something to feed the program. All other devices are ``dead'' during this time. This mode of programming leads to considerable confusion and frustration on the part of the user, and is totally unacceptable.
To deal better with this situation the ``Sample'' and ``Event'' modes of input were introduced [10]. In the former, the programmer would use a Big Loop method (used in the last decade in [8] and [17], but still used today) whereby he would write an infinite loop that samples each active device in turn, and responds appropriately to these inputs. The program, a single task, must interpret several input streams simultaneously, a complex programming problem. In addition, time is wasted in this inner loop checking each device, even if it were not being used.
An application using event input services events from an input queue and responds to each in turn. As with sample input, the application would have to be prepared to handle any incoming input, but would not have to deal with inputs from idle devices. Both sample and event input become reasonable for use with multiple device input if they are used in a system that supports the use of multiple communicating tasks to perform an application. Without such multi-tasking, the difficulty in programming complete multiple-device input leads to inconsistencies and idiosyncrasies. The Apple Macintosh, with its laudable use of direct manipulation, illustrates both the difficulty of programming to handle multiple inputs in a single-task environment and the resulting problems. An example of these idiosyncrasies occurs when one is working with the Macintosh clipboard. The mouse, when pointing to the clipboard window, is one device but it is a second device when pointing to the surrounding window. The user does have more than one virtual locator device, but, due to the lack of multi-tasking, the application window is dead. To resume work on the application the clipboard must be removed. This is akin to having to turn off the car radio to use the steering wheel.
A number of recent systems, all using some form of multi-tasking, have been written to better support multi-thread input. Ten Hagen and Derksen describe ``Dialogue Cells'' as units ``that completely specify one step in a dialogue'' [15]. Any number of these cells may be active at one time, and they may be organized into hierarchies. Each cell specifies the user's action, the system's corresponding reaction, the effect on the system's state, and the environment and conditions in which the action takes place.
Jacob describes a similar but simpler system whereby one may specify a multi-thread state transition table [6]. While good for window-based dialogues, it does not permit truly parallel input.
Tanner, et al., have developed Adagio [9,13,14], based on the multi-tasking operating system Harmony and on anthropomorphic programming ideas [1]. Applications are programmed as a set of many tasks. Multi-thread input is handled by routing the different threads to different tasks through a switchboard. Independently, Lantz [7] has developed a similar model based on the V system, a multi-tasking operating system related to Harmony.
While Adagio relies on synchronous message passing, Hill's Sassafras UIMS uses an asynchronous message passing scheme called a local event broadcast method [5]. This plus his technique of specifying the syntax of the concurrent dialogues makes the system perhaps one of the most complete of the examples cited here.
A final system that treats multi-thread input is the George Washington UIMS, an object-based system that keeps the various input threads separated on separate inter-object message paths [12]. Input tokens are treated as messages that are passed along a chain of objects where each object treats the input lexically, syntactically, or semantically, depending on its role.
These descriptions of current systems, although brief, serve to introduce them as they provide examples of multi-thread input, and can help to lead to a set of requirements for such input. A more thorough comparison of the capabilities and designs of these systems would be a valuable addition to the interaction literature. All the systems are complex, and are best studied by referring to the references cited.
Multi-thread support — requirements
At this time it is appropriate for a workshop on interaction to acknowledge the importance of multi-thread input, and come up with design goals and requirements based on knowledge of systems such as those mentioned above. The following list is a very simple example of such a list, but one that may serve as a starting point for discussions leading to a more complete list.
A UIMS that supports the implementation of multi-thread input should provide the following.
 The ability to separate and keep separate the multiple threads.
 A means for specifying each of the dialogues. [5,6,12,15] all give examples of dialogue specification. Issues as to the relationships between the threads must be addressed. For example, if the processing of a button push and a joy-stick motion were completely independent, a button push, occurring significantly before a joy-stick motion might be semantically interpreted after the interpretation of the joy-stick. If the semantic interpretations of the actions were completely independent, that would not be a problem, however, if they were related, such a situation might not be acceptable.
 Support for calling upon application routines to perform required actions. Note that this requires some form of multi-tasking or task-queuing as several such application tasks could be simultaneously active.
 Means for simultaneous manipulation of a single data structure. Many of the functions performed by the parallel application tasks mentioned above will be modifications to the data structures of the application (Text, geometric data, music data, etc.) A data structure administrator/server must be provided for this purpose.
 Support for multi-task access to the display device (a special case of the above capability). Current window systems permit tasks to be associated with windows as long as all graphics output goes through a single graphics task. However support is needed so that several tasks may connect to a single window. Certain applications may well want to permit tasks to talk directly to the frame buffer (albeit a restricted area of the screen) rather than having a bottle-neck through the window manager.
 Support for device sharing. Particularly in the situation where different input streams go to different tasks, the system must break up the input stream from some physical device into several virtual device streams. [14] describes two approaches to this problem.
 Virtual device capability. There must be an ability to add filters so that input from one or more devices is transformed and is then considered input from a virtual device. Many systems implement this as a hierarchy in their dialogue specification method [5,6,12,15]. Adagio, with its lack of a dialogue specification language implements virtual input devices as tasks that act in the dual role of a consumer of input and a producer of input.
In addition to the capabilities that multi-thread systems must support, it is now appropriate to list ``rules of thumb'' that should guide the interaction design and therefore indicate qualities of interaction that must be encouraged by such a system.
 All devices attached to a system that can be used (including virtual devices) should be continuously active. One could use the slogan ``No Mysteriously Dead Devices''. If the use of a particular device is illogical at some stage of the dialogue, this should be made obvious to the user (by turning off indicator lights on the device or using a technique similar to that found in the Macintosh menus where inappropriate menu items are posted in a faint script), or its use should result in some message indicating why it cannot be used.
 Actions should be ``rapid, incremental, reversible operations whose impact on the object of interest is immediately visible'' [11]. Moded interfaces, requiring state change requests, work against this direct manipulation goal.
 Actions should be interruptable and continuable. In systems that permit truly parallel dialogues this is accomplished to some degree from the fact that any dialogue can be abandoned temporarily then resumed. The Adagio system [13] provides additional support for suspending any menu-selected operation. Jacob's system [6], allows the design of the dialogue to specify where dialogue suspensions can occur.
Conclusion
This paper is intended to serve as a very preliminary attempt at listing the needs and requirements of multi-thread UIMS support. It should be noted that of all the referenced systems that provide such support, none is in general use outside of research laboratories. Four years ago, the previous Seattle workshop [16] helped to organize and publicize ongoing work on UIMS's and in doing so aided the subsequent spurt in their development. However, when it comes to multiple input, the single-task support on which these UIMS's were based is a straight-jacket that forces the programmer to handle everything in an awkward manner. This year's workshop should see the attention focused on enriching the possibilities of parallel input in UIMS's. Effort will be required to define a programmer's model of a UIMS that supports multi-thread input together with support for simultaneously active menus, icons, dialogue boxes, and an application programmed as multiple modules.
Acknowledgements
The author would like to thank Marceli Wein and Kellogg Booth for their comments on earlier drafts of this paper.
References
[1] Booth, K.S., Schaeffer, J. and Gentleman, W.M. Anthropomorphic Programming. University of Waterloo, CS8247, Feb. 1984.
[2] Brooks, F.P. Jr. The Computer ``Scientist'' as Toolsmith — Studies in Interactive Computer Graphics. Information Processing '77, Proc. of IFIP Congress '77, (August 1977), 625634.
[3] Buxton, W. and Myers B.A. A study in two-handed input. In Proceedings CHI'86 Conference on Human Factors in Computing Systems (Boston, April 1317, 1986), ACM, New York, 321-326.
[4] Buxton, W.A. There's More to Interaction than Meets the Eye: Some Issues in Manual Input. In User Centered System Design, Norman, D.A. and Draper, S.W., (eds.) Lawrence Erlbaum Assoc., 1986, 319337.
[5] Hill, R.D. Supporting Concurrency, Communication and Synchronization in Human-Computer Interaction — The Sassafras UIMS. To appear in ACM Transactions on Graphics, 1987.
[6] Jacob, R.J.K. A Specification Language for Direct Manipulation User Interfaces. Submitted for publication.
[7] Lantz, K.A. On user interface reference models. SIGCHI Bulletin 18, 2, (October, 1986), 36-42.
[8] Lipscomb, J., Pique, M., Brooks, F.P., and Wright, W.V. The GRIP-75 man-machine interface [videotape]. SIGGRAPH Video Review 4. (1981).
[9] Mackay, S.A. and Tanner, P.P. Graphics Tools in Adagio, A Robotics Multitasking Multiprocessor Workstation. Proceedings of Graphics Interface '86, (May 1986), 98103.
[10] Rosenthal, D.S.H., Michener, J.C., Pfaff, G., Kessener, R. and Sabin, M. The Detailed Semantics of Graphics Input Devices. Proceedings of SIGGRAPH'82 (Boston, Mass., July 2630, 1982). In Computer Graphics 16, 3 (July 1982), 3338.
[11] Shneiderman, B. Direct manipulation: a step beyond programming languages, IEEE Computer 16, 8 (1983), 5769.
[12] Sibert, J.L., Hurley, W.D. and Bleser, T.W. An Object-Oriented User Interface Management System, Proceedings of SIGGRAPH'86 (Dallas, Texas, August 1822, 1986). In Computer Graphics 20, 4 (August 1986), 259268.
[13] Tanner, P.P., Wein, M., Gentleman, W.M., MacKay S.A. and Stewart D.A. The user interface of Adagio: A robotics multitasking multiprocessor workstation. In Proc. 1st International Conference on Computer Workstations, (November 1985). IEEE, 90-98.
[14] Tanner, P.P., Mackay, S.A., Stewart, D.A. and Wein, M. A Multitasking Switchboard Approach to User Interface Management, Proceedings of SIGGRAPH'86 (Dallas, Texas, August 1822, 1986). In Computer Graphics 20, 4 (August 1986), 241248.
[15] ten aHagen, P.J.W. and Derksen, J. User Interface Management Systems. In User Interface Management Systems, Pfaff, G.E. (ed.) Springer-Verlag, 1985, 109-124.
[16] Thomas, J.J. and Hamlin, G. Graphical Input Interaction Techniques. Computer Graphics 17, 1 (January 1983), 5-66.
[17] Wein, M., Tanner, P.P, and Evans, K.B. Graphics Interaction at NRC [videotape]. SIGGRAPH Video Review 4, (1981), ACM, New York.