From RAGS to RICHES: Exploiting the Potential of a Flexible Generation Architecture

The RAGS proposals for generic specification of NLG systems includes a detailed account of data representation, but only an outline view of processing aspects. In this paper we introduce a modular processing architecture with a concrete implementation which aims to meet the RAGS goals of transparency and reusability. We illustrate the model with the RICHES system -- a generation system built from simple linguistically-motivated modules.

Introduction
As part of the RAGS (Reference Architecture for Generation Systems) project,  introduces a framework for the representation of data in NLG systems, the RAGS 'data model'. This model offers a formally well-defined declarative representation language, which supports the complex and dynamic data requirements of generation systems, e.g. different levels of representation (conceptual to syntax), mixed representations that cut across levels, partial and shared structures and 'canned' representations. However £ We would like to acknowledge the financial support of the EPSRC (RAGS -Reference Architecture for Generation Systems: grant GR/L77102 to Donia Scott), as well as the intellectual contribution of our partners at Edinburgh (Chris Mellish and Mike Reape: grant GR/L77041 to Mellish) and other colleagues at the ITRI, especially Nedjet Bouayad-Agha. We would also like to acknowledge the contribution of colleagues who worked on the RICHES system previously: Neil Tipper and Rodger Kibble. We are grateful to our anonymous referees for their helpful comments. RAGS, as described in that paper, says very little about the functional structure of an NLG system, or the issues arising from more complex processing regimes (see for example Robin (1994), Inuie et al., (1992) for further discussion).
NLG systems, especially end-to-end, applied NLG systems, have many functionalities in common. Reiter (1994) proposed an analysis of such systems in terms of a simple three stage pipeline. More recently Cahill et al (1999) attempted to repeat the analysis, but found that while most systems did implement a pipeline, they did not implement the same pipeline -different functionalities occurred in different ways and different orders in different systems. But this survey did identify a number of core functionalities which seem to occur during the execution of most systems. In order to accommodate this result, a 'process model' was sketched which aimed to support both pipelines and more complex control regimes in a flexible but structured way (see (Cahill et al., 1999), (RAGS, 2000)). In this paper, we describe our attempts to test these ideas in a simple NLG application that is based on a concrete realisation of such an architecture 1 . The RAGS data model aims to promote comparability and re-usability in the NLG research community, as well as insight into the organisation and processing of linguistic data in NLG. The present work has similar goals for the processing aspects: to propose a general approach to organising whole NLG systems in a way which promotes the same ideals. In addition, we aim to test the claims that the RAGS data model approach supports the flexible processing of information in an NLG setting.

The RAGS data model
The starting point for our work here is the RAGS data model as presented in . This model distinguishes the following five levels of data representation that underpin the generation process: The representations aim to cover the core common requirements of NLG systems, while avoiding over-commitment on less clearly agreed issues relating to conceptual representation on the one hand and concrete syntax and document rendering on the other. When one considers processing aspects, however, the picture tends to be a lot less tidy: typical modules in real NLG systems often manipulate data at several levels at once, building structures incrementally, and often working with 'mixed' structures, which include information from more than one level. Furthermore this characteristic remains even when one considers more purely functionally-motivated 'abstract' NLG modules. For example, Referring Expression Generation, commonly viewed as a single task, needs to have access to at least rhetorical and document information as well as referencing and adding to the syntactic information.
To accommodate this, the RAGS data model includes a more concrete representational proposal, called the 'whiteboard' (Calder et al., 1999), in which all the data levels can be represented in a common framework consisting of networks of typed 'objects' connected by typed 'arrows'. This lingua franca allows NLG modules to manipulate data flexibly and consistently. It also facilitates modular design of NLG systems, and reusability of modules and data sets. However, it does not in itself say anything about how modules in such a system might interact.
This paper describes a concrete realisation of the RAGS object and arrows model, OASYS, as applied to a simple but flexible NLG system called RICHES. This is not the first such realisation:  describes a partial re-implementation of the 'Caption Generation System' (Mittal et al., 1999) which includes an objects and arrows 'whiteboard'. The OASYS system includes more specific proposals for processing and inter-module communication, and RICHES demonstrates how this can be used to support a modular architecture based on small scale functionally-motivated units. Together these components provide a central core for RAGS-style NLG applications, allowing separate parts of NLG functionality to be specified in independent modules, which communicate exclusively via the OASYS server.

OASYS (Objects and Arrows
The O/A data representation is a simple typed network representation language. An O/A database consists of a collection of objects, each of which has a unique identifier and a type, and arrows, each of which has a unique identifier, a type, and source and target objects. Such a database can be viewed as a (possibly disconnected) directed network representation: the figures in section 5 give examples of such networks.
OASYS pre-defines object and arrow types required to support the RAGS data model. Two arrow types, el (element) and el(<integer>), are used to build up basic network structuresel identifies its target as a member of the set represented by its source, el (3), identifies its target as the third element of the tuple represented by its source. Arrow type realised by relates structures at different levels of representation. for example, indicating that this SemRep object is realised by this SynRep object. Arrow type revised to provides for support for nondestructive modification of a structure, mapping from an object to another of the same type that can be viewed as a revision of it. Arrow type refers to allows an object at one level to indirectly refer to an object at a different level. Object types correspond to the types of the RAGS data model, and are either atomic, tuples, sets or sequences. For example, document structures are built out of DocRep (a 2-tuple), DocAttr (a set of DocFeatAtoms -feature-value pairs), DocRe-pSeq (a sequence of DocReps or DocLeafs) and DocLeafs.
The active database server supports multiple independent O/A databases. Individual modules of an application publish and retrieve objects and arrows on databases, incrementally building the 'higher level', data structures. Modules communicate by accessing a shared database. Flow of control in the application is event-based: the OASYS module has the central thread of execution, calls to OASYS generate 'events', and modules are implemented as event handlers. A module registers interest in particular kinds of events, and when those events occur, the module's hander is called to deal with them, which typically will involve inspecting the database and adding more structure (which generates further events).
OASYS supports three kinds of events: publish events occur whenever an object or arrow is published in a database, module lifecycle events occur whenever a new module starts up or terminates, and synthetic events -arbitrary messages passed between the modules, but not interpreted by OASYS itself -may be generated by modules at any time. An application starts up by initialising all its modules. This generates initialise events, which at least one module must respond to, generating further events which other modules may respond to, and so on, until no new events are generated, at which point OASYS generates finalise events for all the modules and terminates them.
This framework supports a wide range of architectural possibilities. Publish events can be used to make a module wake up whenever data of a particular sort becomes available for processing. Lifecycle events provide, among other things, an easy way to do pipelining: the second module in a pipeline waits for the finalise event of the first and then starts processing, the third waits similarly for the second to finalise etc. Synthetic events allow modules to tell each other more explicitly that some data is ready for processing, in situation where simple publication of an object is not enough.
RICHES includes examples of all three regimes: the first three modules are pipelined using lifecycle events; LC and RE, FLO and REND interact using synthetic events; while SF watches the database specifically for publication events.

RICHES
The RICHES system is a simple generation system that takes as input rhetorical plans and produces patient advice texts. The texts are intended to resemble those found at the PharmWeb site (http://www.pharmweb.net). These are simple instructional texts telling patients how to use certain types of medicines, such as nosedrops, eye drops, suppositories etc.. An example text from PharmWeb is shown in figure 1, alongside the corresponding text produced by RICHES.
The main aim of RICHES is to demonstrate the feasibility of a system based on both the RAGS data model and the OASYS server model. The modules collectively construct and access the data representations in a shared blackboard space and this allows the modules to be defined in terms of their functional role, rather than say, the kind of data they manipulate or their position in a processing pipeline. Each of the modules in the sys-How to Use Nose Drops 1. Blow your nose gently, so that it is clear.

Wash your hands.
3. Unscrew the top of the bottle and draw some liquid into the dropper.

Tilt your head back.
5. Hold the dropper just above your nose and put the correct number of drops into your nostril.
6. DO NOT let the dropper touch the inside of your nose. 7. Keep your head tilted back for two to three minutes to help the drops run to the back of your nose.
8. Replace the top on the bottle.

PharmWeb -Copyright©1994-2001. All rights reserved
Blow your nose so that it is clear.

Wash your hands
Unscrew the top. Then draw the liquid into the dropper.
Tilt your head back Hold the dropper above your nose. Then put the drops into your nostril.
The dropper must not touch the inside.
Keep your head tilted back for two to three minutes so that the drops run to the back. tem is in itself very simple -our primary interest here is in the way they interact. Figure 2 shows the structure of the system 2 . The functionality of the individual modules is briefly described below.

Rhetorical Oracle (RO)
The input to the system is a RhetRep of the document to be generated: a tree with internal nodes labelled with (RST-style) rhetorical relations and RhetLeaves referring to semantic proposition representations (SemReps). RO simply accesses such a representation from a data file and initialises the OASYS database. tures, annotated with their SemReps, are part of the picture library, and Media Selection builds small pieces of DocRep referencing the pictures.

Document Planner (DP)
The Document Planner, based on the ICONOCLAST text planner (Power, 2000) takes the input RhetRep and produces a document structure (DocRep). This specifies aspects such as the text-level (e.g., paragraph, sentence) and the relative ordering of propositions in the DocRep.
Its leaves refer to SynReps corresponding to syntactic phrases. This module is pipelined after MS, to make sure that it takes account of any pictures that have been included in the document.
Lexical Choice (LC) Lexical choice happens in two stages. In the first stage, LC chooses the lexical items for the predicate of each SynRep. This fixes the basic syntactic structure of the proposition, and the valency mapping between semantic and syntactic arguments. At this point the basic document structure is complete, and the LC advises REND and SF that they can start processing. LC then goes into a second phase, in- terleaved with RE and FLO: for each sentence, RE determines the referring expressions for each noun phrase, LC then lexicalises them, and when the sentence is complete FLO invokes LinGO to realise them.

Referring Expressions (RE) The Referring
Expression module adapts the SynReps to add information about the form of a noun phrase. It decides whether it should be a pronoun, a definite noun phrase or an indefinite noun phrase.

Sentence Finaliser (SF)
The Sentence Finaliser carries out high level sentential organisation. LC and RE together build individual syntactic phrases, but do not combine them into whole sentences. SF uses rhetorical and document structure information to decide how to complete the syntactic representations, for example, combining main and subordinate clauses. In addition, SF decides whether a sentence should be imperative, depending on who the reader of the document is (an input parameter to the system).
Finalise Lexical Output (FLO) RICHES uses an external sentence realiser component with its own non-RAGS input specification. FLO provides the interface to this realiser, extracting (mostly syntactic) information from OASYS and converting it to the appropriate form for the realiser. Currently, FLO supports the LinGO realiser (Carroll et al., 1999), but we are also looking at FLO modules for RealPro (Lavoie and Rambow, 1997) and FUF/SURGE (Elhadad et al., 1997).

Renderer (REND)
The Renderer is the module that puts the concrete document together. Guided by the document structure, it produces HTML formatting for the text and positions and references the pictures. Individual sentences are produced for it by LinGO, via the FLO interface. FLO actually processes sentences independently of REND, so when REND makes a request, either the sentence is there already, or the request is queued, and serviced when it becomes available.

LinGO
The LinGO realiser uses a widecoverage grammar of English in the LKB HPSG framework, (Copestake and Flickinger, 2000). The tactical generation component accepts input in the Minimal Recursion Semantics formalism and produces the target text using a chartdriven algorithm with an optimised treatment of modification (Carroll et al., 1999). No domainspecific tuning of the grammar was required for the RICHES system, only a few additions to the lexicon were necessary.

An example: generation in RICHES
In this section we show how RICHES generates the first sentence of the example text, Blow your nose so that it is clear and the picture that accompanies the text.
The system starts with a rhetorical representation (RhetRep) provided by the RO (see Figure 3) 3 . The first active module to run is MS which traverses the RhetRep looking at the semantic propositions labelling the RhetRep leaves, to see if any can be illustrated by pictures in the picture library. Each picture in the library is encoded with a semantic representation. Matching between propositions and pictures is based on the algorithm presented in Van Deemter (1999) which selects the most informative picture whose representation contains nothing that is not contained in the proposition. For each picture that will be included, a leaf node of document representation is created and a realised by arrow is added to it from the semantic proposition object (see Figure  4).  the sentence is an imperative one). SF waits for the syntactic structure of indvidual clauses to be complete, and then inspects the syntactic, rhetorical and document structure to decide how to combine clauses. In the example, it decides to represent the rhetorical 'motivation' relation within a single text sentence by using the subordinator 'so that'. It also makes the main clause an imperative, and the subordinate clause indicative.
As soon as SF completes a whole syntactic sentence, FLO notices, and extracts the information required to interface to LinGO with an MRS structure. The string of words returned by LinGO, is stored internally by FLO until REND requests it.
Finally, REND draws together all the information from the document and syntactic structures, and the realiser outputs provided by FLO, and produces HTML. The entire resultant text can be seen on the right hand side of figure 1.


A Fast Algorithm for Transistor Folding

Transistor folding reduces the area of row-based designs that employ transistors of different size. Kim and Kang [1] have developed an O(m2 log m) algorithm to optimally fold m transistor pairs. In this paper we develop an O(m2) algorithm for optimal transistor folding. Our experiments indicate that our algorithm runs 3 to 60 times as fast for m values in the range (100, 100,000).

INTRODUCTION
In high-performance circuit design, the transistor sizing problem was investigated widely in the past (for example, [7][8][9][10]). The objective of transistor sizing is to reduce the circuit delay by increasing the area of transistors. One by-product of transistor sizing is the generation of layouts of transistors of widely varying size. In row-based layout synthesis ( [3][4][5][6]), we group pMOS and nMOS transistors together and place them in rows. The layout area for these designs is wasted due to nonuniform cell heights. The layout area required can be reduced by folding large transistors so that their height is reduced. Transistor folding to optimize layout area has been considered in [1] and [2]. Her and Wong [2]  They also show that the area of row-based designs can be reduced by as much as 30% by performing transistor folding. In this paper, we consider the row-based-design transistor-folding problem considered in [1] and develop an O(m2) or O(s(m algorithm to minimize area. We also report on experiments conducted by us that show that our algorithm actually runs much faster than the This research was supported, in part, by the Army Research Office under grant DAA H04-95-1-0111. e-mail: yccheng@cise.ufl.edu *Corresponding author, e-mail: sahni@cise.ufl.edu algorithm of [1]. The test circuits used in our experiments have between 100 and 100,000 transistor pairs. So, our tests are similar to those conducted in [1] where the circuits had from 192 to 88,258 transistor pairs.

PROBLEM FORMULATION
We are given a CMOS circuit with a row of m transistor pairs. Each transistor pair consists of a pMOS transistor and its dual nMOS transistor. Let Pi and n;, respectively, be the heights of the pMOS and nMOS transistors in the ith pair, _< < m. Pi and ni are integers that give transistor height in multiples of the minimum resolution A. occupied by the folded transistor pair is shown by a shaded box in Figure 2. In practice, the height of the layout area is slightly larger than the sum of the pMOS and nMOS folding heights, and the layout width is slightly larger than the number of transistor columns because of overheads.
Let hp and hn be the folded heights of the pMOS and nMOS transistors, respectively. The height of the folded layout is hp+h,+cv and the width is -i%1 max((pi/hp), (ni/hn)]) / ch where cv and ch are, respectively, vertical and horizontal overheads. The area of the folded layout is [ [1].
The second algorithm given in [1] works in two phases. In the first phase, the algorithm constructs a subset S P of [PMIN, max(P)] and another subset S u of [NMIN, max(N)] with the property that the optimal hp is in S e and the optimal hn is in Su. The basic observation used to arrive at S e and S u is that if the heights hi and hi /k divide a transistor into the same number of columns then hi is preferred over hi +k (for example if Pl 14, then folding heights 7,8,9,10,11,12 and 13 all fold the transistor into two columns; 7 is preferred over the remaining choices). In the second phase the opti- Our algorithm is also a two phase algorithm. The first phase of our algorithm is identical to the first phase of Kim and Kang's algorithm [1]. We compute the subsets S e and S N using the code of Figure 3. The arrays SPL and SNL are initialized to zero in the first two for loops. Then we determine the members of S e and sN; we set SPL [i] if and only if E S e and SNL [i] if and only if SN. Finally, S e and S N are computed in compact form from SPL and SNL respectively. Note that we can compute S e and S N in either ascending or descending order easily by controlling the direction of traversal of the SNL and SPL arrays respectively, in the last two for loops. The algorithm presented in Figure 3 computes S e in ascending order and S N in decending order.

Phase II
Assume that the transistor pairs have been recorded so that (pi/ni)<_ ((Pi+l)/(ni+l)); also assume that (po/no)=0 and ((pm+,)/(nm+))= OC. The formula, Eq. (1) 4 Compute optimal hp and h,.  Figure 4. Since S P and S u can be computed in ascending and descending order respectively by Algorithm Phase I of Figure 3, no sorting is needed to evaluate the members of S P and S u in the specified order. We can sort the transistors into increasing (actually nondecreasing) order of (pi/ni) in Algorithm Refined Phase II (P, N, SP, SN, Ch, Cv) /* S P is in ascending order and S N is in descending order */  Figure 5. Although its worstcase complexity is the same as that of Figure 4, it is expected to run faster in practice.
processing is completed using the technique of Kim and Kang [1], it is possible that the cost of this preprocessing when used in conjunction with our refined Phase II algorithm of Figure 5 may exceed the benefits that accrue from the preprocessing. Therefore, we formulate another version of our algorithm which does not employ the Phase I preprocessing algorithm of Figure 3. The new version, Figure 6 is just the algorithm of Figure 5 with the while loops replaced by for loops. Figure 7 shows a variant of the algorithm of Figure 6 in which only one of the arrays Lp and L N is precomputed, the values of the other array are computed as needed. This variant reduces the space requirements of the algorithm, and, as we shall see, also reduces the time requirements.

ALGORITHMIC VARIANTS
Although the use of the preprocessing phase, Phase I, dramatically reduces the run time when The phase algorithm of Figure 3, the phase 2 algorithm of Figure 5, the algorithmic variants of Figures 6 and 7, and the two algorithms of [1]  methodologies were used to develop the codes for our algorithms and those of [1]. As a result, we expect that almost all of the performance difference exhibited in our experiments is due to algorithmic rather than programming differences. Since we were unable to obtain the test data used in [1], we generated random data. We ignore any possible correlation between pMOS and nMOS transistors. For our test data, the number of transistor pairs ranged from 100 to 100,000. This covers the range in transistor numbers (192 to 88,258) in the circuits of [1]. For our first test set, the sizes of the pMOS and nMOS transistors were generated using a uniform random number generator with range [30,90] for pMOS and [20, 60] for nMOS. These size ranges correspond to those for the circuit fract that was used in [1], the circuit fract has 598 transistors. Since all of the tested algorithms generate optimal solutions, run time is the only comparative factor. This time is provided in Table I. Other than in the column labeled "Phase 1", all times are the times needed for the entire area minimization process (i.e., phase plus phase 2).
The exhaustive search algorithm was not run for m > 10,000 as its run time becomes prohibitive.
In the case of the algorithm proposed in [1], the phase 2 time is significantly larger than the phase time. Our algorithm for phase 2 (5) has brought this time down to approximate the phase time. Equally interestingly, on the data sets used by us, the preprocessing of phase is no longer of any use. When this preprocessing is eliminated (as in Fig. 6), the run time reduces by an additional 30%. The variant of Figure 7 provides modest run time improvement (due mainly to not having to reference a two-dimensional array to get one of the L values), but provides a 50% reduction in space needs.
For small circuits (m <_ 10,000), our algorithm of Figure 7 provides a speedup of 3.8 to 7.1 over the algorithm of [1]. On larger circuits, the speedup is more dramatic. For instance, when m--= 100,000 our algorithm of Figure 7 is almost 27 times as fast as that of [1].
We experimented with two other data sets. Table II reports the run times for circuits in which the range of the uniform random number generator was set to [30,180] for pMOS transistor sizes and [20, 120] for nMOS sizes and Table III gives the run times when the transistor sizes are

CONCLUSION
We have developed a transistor folding algorithm that is both theoretically and practically faster than the algorithm proposed in [1]. Our algorithm is also simpler to code. Experiments suggest that our algorithm runs 3 to 60 times as fast as the algorithm of [1] on circuits with 100 to 100,000 transistor pairs. These circuit sizes are comparable to those used in [1].


Scalable Unix Commands for Parallel Processors: A High-Performance Implementation

We describe a family of MPI applications we call the Parallel Unix Commands. These commands are natural parallel versions of common Unix user commands such as ls, ps, and find, together with a few similar commands particular to the parallel environment. We describe the design and implementation of these programs and present some performance results on a 256-node Linux cluster. The Parallel Unix Commands are open source and freely available.

Introduction
The oldest Unix commands (ls, ps, find, grep, etc.) are built into the fingers of experienced Unix users. Their usefulness has endured in the age of the GUI not only because of their simple, straightforward design but also because of the way they work together. Nearly all of them do I/O through stdin and stdout, which can be redirected from/to files or through pipes to other commands. Input and output are lines of text, facilitating interaction among the commands in a way that would be impossible if these commands were GUI based.
In this paper we describe an extension of this set of tools into the parallel environment. Many parallel environments, such as Beowulf clusters and networks of workstations, consist of a collection of individual machines, with at least partially distinct file systems, on which these commands are supported. A user may, however, want to consider the collection of machines as a single parallel computer, and yet still use these commands. Unfortunately, many common tasks, such as listing files in a directory or processes running on each machine, can take unacceptably long times in the parallel environment if performed sequentially, and can produce an inconveniently large amount of output.
A preliminary version of the specification of our Parallel Unix Commands appeared in [4]. New in this paper are a refinement of the specification based on experience, a high-performance implementation based on MPI for improved scalability, and measurements of performance on a 256-node Unix cluster.
The tools described here might be useful in the construction of a clustermanagement system, but this collection of user commands does not itself purport to be a cluster-management system, which needs more specialized commands and a more extensive degree of fault tolerance. Although nothing prevents these commands from being run by root or being integrated into cluster-management scripts, their primary anticipated use is the same as that of the classic Unix commands: interactive use by ordinary users to carry out their ordinary tasks.

Design
In this section we describe the general principles behind this design and then the specification of the tools in detail.

Goals
The goals for this set of tools are threefold: -They should be familiar to Unix users. They should have easy-to-remember names (we chose pt<unix-command-name>) and take the same arguments as their traditional counterparts to the extent consistent with the other goals. -They should interact well with other Unix tools by producing output that can be piped to other commands for further processing, facilitating the construction of specialized commands on the command line in the classic Unix tradition. -They should run at interactive speeds, as do traditional Unix commands.
Parallel process managers now exist that can start MPI programs quickly, offering the same experience of immediate interaction with the parallel machine, while providing information from numerous individual machines.

Specifying Hosts
All the commands use the same approach to specifying the collection of hosts on which the given command is to run. A host list can be given either explicitly, as in the blank-separated list 'donner dasher blitzen', or implicitly in the form of a pattern like ccn%d@1-32,42,65-96, which represents the list ccn1,...,ccn32,ccn42,ccn65,...,ccn96. All of the commands described below have a hosts argument as an (optional) first argument. If the environment variable PT MACHINE FILE is set, then the list of hosts is read from the file named by the value of that variable. Otherwise the first argument of a command is one of the following: -all all of the hosts on which the user is allowed to run, -m the following argument is the name of a file containing the host names, -M the following argument is an explicit or pattern-based list of machines.

The Commands
The Parallel Unix Commands are shown in Table 1. They are of three types: straightforward parallel versions of traditional commands with little or no output; parallel versions of traditional commands with specially formatted output; and new commands in the spirit of the traditional commands but particularly inspired by the parallel environment. Parallel Versions of Traditional Commands The first part of Table 1 lists the commands that are simply common Unix commands that are to be run on each host. The semantics for many of these is very natural -the corresponding uniprocessor version of any command is run on every node specified. For example, the command ptrm -M "node%d@1-5" -rf old_files/ is equivalent to running rm -rf old_files/ on node1, node2, node3, node4, and node5. The command line arguments to most of the commands have the same meaning as their uniprocessor counterparts. The exceptions ptcp and ptmv deserve special mention; the semantics of parallel copy and move are not necessarily obvious. The commands presented here perform one-to-many copies by using MPI and compression; ptmv deletes the local files that were copied if the copy was successful. The command line arguments for ptcp and ptmv are identical to their uniprocessor counterparts with the exception of an option flag, -o. This flag allows the user to specify whether compression is used in the transfer of data. In the future the flags may be expanded to allow for other customizations. Handling of directories as either source or destination is handled as in the normal version of cp or mv.
Parallel test also deserves explanation. There are two versions of parallel test; both run test on all specified nodes, but pttesta logically ANDs the results of the tests, while pttesto logically ORs the results of the tests. By default, pttest is an alias for pttesto. This link allows the natural semantics of pttest to detect failure on any node.
Parallel Versions of Common UNIX Commands with Formatted Output The second set of commands in Table 1 may produce a significant amount of output. In order to facilitate handling of this output, if the first argument to ptfind, ptls, or ptcat is -h (for "headers"), then the output from each host will be preceded by a line identifying the host. This is useful for piping into other commands such as ptdisp (see below). In the example the user has file myfile1 on node1, no files in the current directory on node2, and the files myfile1 and myfile2 on node3. All other command line arguments to these commands have the same meaning as their uniprocessor counterparts.
To facilitate processing later in a pipeline by filters such as grep, we provide a filter that spreads the hostname across the lines of output, that is, $ ptls -M "node%d@1-3" -h | ptspread node1.domain.tld: myfile1 node3.domain.tld: myfile1 node3.domain.tld: myfile2 New parallel commands The third part of Table 1 lists commands that are in the spirit of the other commands but have no non-parallel counterpart.
Many of the uses of ps are similar to the uses of ls, such as determining the age of a process (respectively, a file) or owner of a process (respectively, a file). Since a Unix file system typically contains a large number of files, the Unix command find, with its famously awkward syntax, provides a way to search the file system for files with certain combinations of properties. On a single system, there are typically not so many processes running that they cannot be perused with ps piped to grep, but on a parallel system with even a moderate number of hosts, a ptps could produce thousands of lines of output. Therefore, we have proposed and implemented a counterpart to find, called ptfps, that searches the process space instead of the file space. In the Unix tradition we retain the syntax of find. Thus ptfps -all -user lusk will list all the processes belonging to user lusk on all the machines in a format similar to the output of ps, and ptfps -all -user gropp -time 3600 -cmd^mpd will list all processes owned by gropp, executing a command beginning with mpd, that have been running for more than an hour. Many more filtering specifications and output formats are available; see the (long) man page for ptfps for details.
The command ptdistrib is effectively a scheduler for running a command on a set of files over specified nodes. For example, to compile all of the C files in the current directory over all nodes currently available, then fetch back all the resulting files, the user might use the following command:

ptdistrib -all -f 'cc -c {}' *.c
Here, the {} is replaced by the names of the files given, one by one. See the man page for more information.
The command ptexec simply executes a command on all nodes. To determine, for example, which hosts were available for running jobs, the user might run the following command:

ptexec -all hostname
No special formatting of output or return code checking is done.
The command ptpred runs a test on each specified node and outputs a 0 or 1 based on the result of the test. For example, to test for the existence of the file myfile on nodes node1, node2, and node3, the user might have the following session: $ ptpred -M "node1 node2 node3" '-f myfile' node1.domain.tld: 1 node2.domain.tld: 0 node3.domain.tld: 1 In this case, node1 and node3 have the file, but node2 does not. Note that ptpred prints the logical result of test, not the verbatim return value.
The output of ptpred can be customized: $ ptpred -M "node1 node2 node3" '-f myfile' \ 'color black green' 'color black red' node1.domain.tld: color black green node2.domain.tld: color black red node3.domain.tld: color black green This particular customization is useful as input to ptdisp, which is a general display tool for displaying information about large groups of machines. As an example, Figure 1 shows some screenshots produced by ptdisp.
The command ptdisp accepts special input from standard input of the form

<hostname>: <command> [arguments]
where command is one of color, percentage, text, or a number. The output corresponding to each host is assigned to one member of an array of button boxes.
As an example, one might produce the screenshot on the left in Figure 1 with the following command: ptpred -all '-f myfile' 'color black white' \ 'color white black' \ | ptdisp -c -t "Where myfile exists" to find on which nodes a particular file is present. The command ptdisp can confer scalability on the output of other commands not part of this tool set by serving as the last step in any pipeline that prepares lines of input in the form it accepts. Since it reads perpetually, it can even serve as a crude graphical system monitor, showing active machines, as on the right side of Figure 1. The command to produce this display is given in Section 3. The number of button boxes in the display adapts to the input. When the cursor is placed over a box, the node name automatically appears, and clicking on a button box automatically starts an xterm with an ssh to that host if possible, for remote examination.

Examples
Here we demonstrate the flexibility of the command set by presenting a few examples of their use.
-To look for nonstandard configuration files: ptcp -all mpd.cfg /tmp/stdconfig; \ ptexec -all -h diff /etc/mpd.cfg /tmp/stdconfig \ | ptspread This shows differences between a standard file and the version on each node.
-To continuously monitor the state of the machine (nodes up or down) (echo "$LEGEND$: Active black green Inactive black red"; \ while true; do (enumnodes -M 'ccn%d@1-256' \ | awk '{print $1 ": 0"}') ; sh ptping.sh 'ccn%d@1-256'; \ sleep 5; done) | ptdisp -t "Active machines" -c We assume here that ptping pings all the nodes. This is admittedly ugly, but it illustrates the power of the Unix command line and the interoperability of Unix commands. The output of this command is what appears on the right side of Figure 1.
-To kill a runaway job ptfps -all -user ong -time 10000 -kill SIGTERM

Implementation
The availability of parallel process managers, such as MPD [2], that provide pre-emption of existing long-running jobs and fast startup of MPI jobs, has made it possible to write these commands as MPI application programs. Each command parses its hostlist arguments and then starts an MPI program (with mpirun or mpiexec) on the appropriate set of hosts. It is assumed that the process manager and MPI implementation can manage stdout from the individual processes in the same way that MPD does, by routing them to the stdout of the mpirun process. The graphical output of ptdisp is provided by GTK+ (See http://www.gtk.org).
Using MPI lets us take advantage of the MPI collective operations for scalability in delivering input arguments and/or data and collecting results. Some of the specific uses of MPI collective operations are as follows.
-MPI Bcast uses ptcp to move data to the target nodes.
-MPI Reduce, with MPI MIN as the reduction operation, is used in many commands for error checking. -MPI Reduce, with MPI LOR or MPI LAND as the reduction operation, is used in pttest.
-MPI Gather is used in ptdistrib to collect data enabling dynamic reconfiguration of the list of nodes work is distributed to. -Dynamically-created MPI communicators other than MPI COMM WORLD are used when the task is different on different nodes. An example of this situation occurs when the target specified in the ptcp command turns out to be a file on some nodes and a directory on others.
The implementation of ptcp is roughly that described in [5]. Parallelism is achieved at three levels: writing the file to the local file systems on each host is done in parallel; a scalable implementation of MPI Bcast provides parallelism in the sending of data; and the files are sent in blocks, providing pipeline parallelism. We also use compression to reduce the amount of data that must be transferred over the network. Directory hierarchies are tarred as they are being sent.
A user may have different user ids on different machines. Whether these scalable Unix commands allow for this situation depends on the MPI implementation with which they are linked. In the case of MPICH [3], for example, it is possible for a user to run a single MPI job on a set of machines where the user has different user ids.

Performance
To justify the claims of scalability, we have carried out a small set of experiments on Argonne's 256-node Chiba City cluster [1]. Execution times for simple commands are dominated by parallel process startup time. Commands that require substantial data movement are dominated by the bandwidth of the communication links among the hosts and the algorithms used to move data. Timings for a trivial parallel task and one involving data movement are shown in Table 2. Our copy test copies a 10MB file that is randomly generated and does not compress well. With text data the effective bandwidth would be even higher. In Figure 2  we compare ptpc with two other mechanisms for copying a file to the local file systems on other nodes. The simplest way to do this is to call rcp or scp in a loop. Figure 2 shows how quickly this method becomes inferior to more scalable approaches. The "chi file" curve is for a sophisticated system specifically developed for the Chiba City cluster [1]. This system, written in Perl, takes advantage of the specific topology of the Chiba City network and the way certain file systems are cross-mounted. The general, portable, MPI-based approach used by ptcp performs better.

Conclusion
We have presented a design for an extension of the classical Unix tools to the parallel domain, together with a scalable implementation using MPI. The tools are available at http://www.mcs.anl.gov/mpi. The distribution contains all the necessary programs, complete source code, and man pages for all commands with much more detail than has been possible to present here. An MPI implementation is required; while any implementation should suffice, these commands have been most extensively tested with MPICH [3] and the MPD process manager [2]. The tools are portable and can be installed on parallel machines running Linux, FreeBSD, Solaris, IRIX, or AIX.


Evaluating Text Quality: Judging Output Texts Without a Clear Source

We consider how far two attributes of text quality commonly used in MT evaluation -- intelligibility and fidelity -- apply within NLG. While the former appears to transfer directly, the latter needs to be completely re-interpreted. We make a crucial distinction between the needs of symbolic authors and those of end-readers. We describe a form of textual feedback, based on a controlled language used for specifying software requirements that appears well suited to authors' needs, and an approach for incrementally improving the fidelity of this feedback text to the content model.

Introduction
Probably the most critical questions that need to be addressed when evaluating automatically generated texts are: does the text actually say what it's supposed to say and is it fluent, coherent, clear and grammatical? The answers to these questions say something important about how good the target texts are and -perhaps more to the point -how good the system that generated them is. There is no a priori reason why the target texts should be any better or worse when they result from natural language generation (NLG) or from machine translation (MT): indeed, they could result from the same language generator. Given this, it may be natural to assume that NLG could appropriately adopt evaluation methods developed for its more mature sister, MT. However, while this holds true for issues related to intelligibility (the second critical question), it does not apply as readily to issues of fidelity (the first question). We go beyond our recent experience of evaluating the AGILE system for producing multilingual versions of software user manuals Kruijff et al., 2000) and raise some open questions about how best to evaluate the faithfulness of an output text with respect to its input specification.

Evaluating intelligibility
The use of rating scales to assess the intelligibility of MT output has been widespread since the early days in the field. Typically, monolingual raters assign a score to each sentence in the output text. However, this does not amount to an agreed methodology, since the number of points on the scale and their definition have varied considerably. For example, Carroll (1966) used a nine-point scale where point 1 was defined as "hopelessly unintelligible" and point 9 as "perfectly clear and intelligible"; Nagao and colleagues (Nagao et al., 1985), in contrast, used a five-point scale, while Arnold and his colleagues (Arnold et al., 1994) suggest a four-point discrimination. In evaluating the intelligibility of the AGILE output, we asked professional translators and authors who were native speakers of the languages concerned-Bulgarian, Czech and Russian-to score individual text fragments on a four-point scale. The evaluators were also asked to give a summative assessment of the output's suitability as the first draft of a manual.
In a single pass, AGILE is capable of generating several types of text, each constituting a section of a typical software user manual-i.e., overview, short instructions, full instructions, and functional descriptions-and appearing in one of two styles (personal/direct or impersonal/indirect). We evaluated all of these text types using the same method. The intelligibility evaluation was complemented by an assessment of the grammaticality of the output, conducted by independent native speakers trained in linguistics. Following an approach widely used in MT (e.g., Lehrberger and Bourbeau, 1987), the judges referred to a list of error categories for their annotations.

Evaluating fidelity
In MT, evaluating fidelity (or "accuracy") entails a judgment about the extent to which two texts "say the same thing". Usually, the two texts in question are the source (i.e., original) text and the (machine-)translated text and the judges are expert translators who are again invited to rate the relative information content of pairs of sentences on an anchored scale (e.g., Nagao et al., 1985). But others (e.g., Caroll, 1966) have also compared the informativeness of the machine translation and a human translation deemed to serve as a benchmark. Interestingly, both of these researchers found a high correlation between the intelligibility evaluations and the fidelity evaluations, which suggests that it may be possible to infer fidelity from the (less costly) evaluation of intelligibility. However, at the current state-ofthe-art this approach does not guarantee to detect cases where the translation is perfectly fluent but also quite wrong.
For NLG, the story is rather different. Lacking a source text, we are denied the relatively straightforward approach of detecting discrepancies between artifacts of the same type: texts. The question is, instead, whether the generated text "says the same thing" as the message -i.e., the model of the intended semantic content together with the pragmatic force of the utterance.
The message is clearly only available through an external representation. In translation generally, this external representation is the source text and the task is commonly characterized as identifying the message -which originates in the writer's mental modelin order to re-express it in the target language. In an NLG system, the one external representation that is commonly available is the particular domain model that serves as input to the generation system. This model may have been provided directly by an artificial agent, such as an expert system. Alternatively, it may have been constructed by a human agent as the intended instantiation of their mental model. Yet, whatever its origins, directly comparing this intermediate representation to the output text is problematic.
A recent survey of complete NLG systems (Cahill et al., 1999) found that half of the 18 systems examined accepted input directly from another system 1 . A typical example is the Caption Generation System (Mittal et al., 1998), which produces paragraph-sized captions to accompany the complex graphics generated by SAGE (Roth et al., 1994). The input to generation includes definitions of the graphical constituents that are used to by SAGE to convey information: "spaces (e.g., charts, maps, tables), graphemes (e.g., labels, marks, bars), their properties (e.g., color, shape) and encoders-the frames of reference that enable their properties to be interpreted/translated back to data values (e.g., axes, graphical keys)." 2 For obvious reasons, this does not readily lend itself to direct comparison with the generated text caption.
In the remaining half of the systems covered, the domain model is constructed by the user (usually a domain expert) through a technique that has come to be known as symbolic authoring: the 'author' uses a specially-built knowledge editor to construct the symbolic source of the target text. These editors are interfaces that allow authors to build the domain model using a representation that is more 'natural' to them than the artificial language of the knowledge base. 3 The purpose of these representations is to provide feedback intended to make the content of the domain model more available to casual inspection than the knowledge representation language of the domain model. As such, they are obvious candidates as the standard against which to measure the content of the texts that are generated from them.
We first consider the case of feedback presented in graphical mode, and then the option of textual feedback, using the WYSIWYM technology Scott, Power and Evans, 1998). We go on to make recommendations concerning the desirable properties of the feedback text.

Graphical representations of content
Symbolic authoring systems typically make use of graphical representations of the content of the domain model-for example, conceptual graphs (Caldwell and Korelsky, 1994). Once trained in the language of the interface, the domain specialist uses standard text-editing devices such as menu selection and navigation with a cursor, together with standard text-editing actions (e.g., select, copy, paste, delete) to create and edit the content specification of the text to be generated in one or several selected languages.
The user of AGILE, conceived to be a specialist in the domain of the particular software for which the manual is required (i.e., CAD/CAM), models the procedures for how to use the software. AGILE's graphical user interface (Hartley, Power et al., 2000) closely resembles the interface that was developed for an earlier system, DRAFTER, which generates software manuals in English and French (Paris et al., 1995). The design of the interface represents the components of the procedures (e.g., goals, methods, preconditions, sub-steps, side-effects) as differently coloured boxes. The user builds a model of the procedures for using the software by constructing a series of nested boxes and assigning labels to them via menus that enable the selection of concepts from the underlying domain ontology.

The input specification for the user
As part of our evaluation of AGILE, we asked 18 IT professionals 4 to construct a number of predetermined content models of various degrees of complexity and to have the system 4 There were six for each of the three Eastern European languages; all had some (albeit limited) experience of CAD/CAM systems and were fluent speakers of English. generate text from them in specified styles in their native language. Since the evaluation was not conducted in situ with real CAD/CAM system designers creating real draft manuals, we needed to find a way to describe to the evaluators what domain models we wanted them to build. Among the possible options were to give them a copy of either: • the desired model as it would appear to them in the interface (e.g., Figure 1); • the target text that would be produced from the model (e.g., Figure 2); • a 'pseudo-text' that described the model in a form of English that was closer to the language of the AGILE interface than to fluent English (e.g., Figure 3). We rejected the first option because it amounted to a task of replication which could be accomplished successfully even without users having any real understanding of the meaning of Draw a line by specifying its start and end points.
To draw a line Specify the start point of the line. Specify the end point of the line. the model they were building. Therefore, it would shed no light on how users might be able to build a graphical model externalising their own mental model. We discarded the second because a text may not necessarily make any explicit linguistic distinction between different components of the model-for example, between a precondition on a method and the first step in a method consisting of several steps 5 . Thus, in general, target texts may not reflect every distinction available in the underlying domain model (without this necessarily causing any confusion in the mind of the reader). As a result of such underspecification, they are ill-suited to serving as a staring point from which a symbolic author could build a formal model.
We opted, then, for providing our evaluators with a pseudo-text in which there was an explicit and regular relationship between the components of the procedures and their pseudotextual expression. Figure 4 is one of the pseudo-texts used in the evaluation.

Evaluating the fidelity of the output
This particular set-up afforded us the possibility of judging the fidelity of the 'translation' between the following representations: a) desired model and model produced b) model produced and output text c) pseudo-text and model produced d) pseudo-text and the output text 5 For example, between: "To cook a goose: Before starting, make sure the goose has been plucked. Put the goose in a medium oven for 1.5 hours." and "To cook a goose: First pluck the goose. Then put it in a medium oven for 1.5 hours." We focused on (a), which was of course mediated by (c); that is, we focused on the issue of creating an accurate model. This is an easier issue than that of the fidelity of the output text to the model (b), while the representations in (d) are too remote from one another to permit useful comparison.
To measure the correspondence between the actual models and the desired/target models, we adopted the Generation String Accuracy (GSA) metric (Bangalore, Rambow and Whittaker, 2000; used in evaluating the output of a NLG system. It extends the simple Word Accuracy metric suggested in the MT literature (Alshawi et al., 1998), based on the string edit distance between some reference text and the output of the system. As it stands, this metric fails to account for some of the special properties of the text generation task, which involves ordering word tokens. Thus, corrections may involve reordering tokens. In order not to penalise a misplaced constituent twice-as both a deletion and an insertion-the generation accuracy metric treats the deletion (D) of a token from one location and its insertion (I) at another location as a single movement (M). The remaining deletions, insertions, and substitutions (S) are counted separately. Generation accuracy is given by the following equation, where R is the number of (word) tokens in the reference text. For Bangalore and his colleagues, the reference text is the desired text; it is a gold standard given a priori by a corpus representing the target output of the system. The generation accuracy of a string from the actual output of the system is computed on the basis of the number of movements, substitutions, deletions and insertions required to edit the string into the desired form.
In our case, the correspondence was measured between models rather than texts, but we found the metric 'portable'. The tokens are no longer textual strings but semantic entities. Although this method provided a useful quantitative measure of the closeness of the fit of the actual generated text to what was intended, it is not without problems, some of which apply irrespective of whether the metric is applied to texts or to semantic models. For example, it does not capture qualitative differences between the generated object and the reference object, that is, it does not distinguish trivial from serious mistakes. Thus, representing an action as the first step in a procedure rather than as a precondition would have less impact on the end-reader's ability to follow the instructions than would representing a goal as a side-effect. 6

Textual representations of content
Once the model they represent becomes moderately complex, graphical representations prove to be difficult to interpret and unwieldy to visualise and manipulate (Kim, 1990;Petre, 1995). WYSIWYM offers an alternative, textual modality of feedback, which is more intuitive and natural. As we will discuss below, there is a sense in which, in its current form, the feedback text may be too natural.

Current status of WYSIWYM feedback text
The main purpose of the text generated in feedback mode, as currently conceived, is to show the symbolic author the possibilities for further expanding the model under development.
As with AGILE's box representation, clicking on a coloured 'anchor' brings up a menu of legitimate fillers for that particular slot in the content representation. Instantiating green anchors is optional, but all red anchors must be instantiated for a model to be potentially complete ( Figure 5). Once this is the case, authors tend to switch to output mode, which produces a natural text reflecting the specified model and nothing else. In WYSIWYM systems the same generator is used to produce both the feedback and output texts; this means that the feedback text can be as fluent as the output text. In its current instantiations, this is precisely what is produced, even when the generator is capable of producing texts of rather different styles for the different purposes. 7

Feedback in a controlled language
The motivation for generating a new type of feedback text comes from two sources.
The first is the pseudo-texts that we constructed by hand for the AGILE evaluation. As far as the form of the models actually constructed is concerned, they proved consistently reliable guides for the symbolic authors. Where they proved inadequate was in their identification of multiple references to the same domain model entity; several authors tended to create multiple instances of an entity rather than multiple pointers to a single instance. Let us now turn from the testing scenario, where authors have a defined target to hit, and consider instead a production setting where the author is seeking to record a mental model. It is a simple matter to have the system generate a second feedback text, complementing the present one, this time in the style of the pseudo-texts 8 for the purpose of describing unambiguously, if rebarbatively, the state of a potentially complete model.
The second is Attempto Controlled English (ACE: Fuchs and Schwitter, 1996;Fuchs, Schwertel and Schwitter, 1999), which allows domain specialists to interactively formulate software requirements specifications. The specialists are required to learn a number of compositional rules which they must then apply when writing their specifications. These are parsed by the system. For all sentences that it accepts, the system creates a paraphrase ( Figure 6) that indicates its interpretations by means of brackets. These interpretations concern phenomena like anaphoric reference, conjunction and disjunction, attachment of prepositional phrases, relative clauses and quantifier scope. The user either accepts the interpretation or rephrases the input to change it.

Figure 6: ACE paraphrases
The principle of making interpretations explicit appears to be good one in the NLG context too, especially for the person constructing the domain model. Moreover, in the context where the output text is required to be in a controlled language, the use of WYSIWYM relieves the symbolic author of the burden of learning the specialized writing rules of the given control language.
Optimising the formulation of the controlled language feedback is matter of iteratively revising it via the testing scenario, using GSA as the metric, until authors consistently achieve total fidelity of the models they construct with the reference models.

Conclusions
So how can go about judging whether the products of NLG systems express the intended message? A first step towards this goal is to enable symbolic authors to satisfy themselves that they have built the domain model they had in mind. Graphical feedback is too difficult to interpret, while natural language output that is optimised for the end-reader may not show the unequivocal fidelity to the domain model that the symbolic author requires.
We have suggested that textual feedback in a form close to a controlled language used for specifying software requirements is a good candidate for this task. We have further outlined a method for incrementally refining this controlled language by monitoring symbolic authors' ability to construct reference domain models on the basis of controlled language feedback. The trade-off between transparency and naturalness in the output text intended for the end-reader will involve design decisions based on, among other things, reader profiling. Assessing the fidelity of the end-reader text to the model is also a necessary step, but not one that can be conflated with or precede that of validating the accuracy of the model with respect to the author's intentions.