Sean Halle

Albert Cohen

A Mutable Hardware Abstraction to Replace Threads

We propose an abstraction to alleviate the difficulty of programming with threads. This abstraction is not directly usable by application programmers. Instead, applicationvisible behavior is defined through a semantical plugin, and invoked via a language or library that uses the plugin. The main benefit is that parallel language runtimes become simpler to implement, because they use sequential algorithms for the parallel semantics. This is possible because the abstraction makes available a virtual time in which events in different program time-lines are sequentialized. The parallel semantics relate events in different time-lines via relating the sequentialized versions within the virtual time-line. We have implemented the abstraction in user-space and demonstrate its low overhead and quickness to implement a runtime on three sets of parallelism constructs: rendez-vous style send and receive; Cilk style spawn and sync, which have similar performance to Cilk 5.4; and mutex and condition variable constructs from pthreads, which have 80x lower overhead than Linux thread operations. Development time averaged around two days per set, versus an expected duration of weeks to modify a thread-based runtime system.

Motivation

Thread parallelism constructs have been well documented to be difficult to program with. They directly expose low-level concurrency to the programmer. Arbitrary non-deterministic behavior and deadlocks can arise from improperly synchronized code. Efficient execution requires non-blocking algorithms whose correctness require deep understanding of weakly consistent memory models. In addition, the operating system abstraction for threads comes with a very high context-switching and synchronization overhead.

A partial solution. To deal with the last problem, a parallel language's runtime turns off operating system threads by pinning one to each physical core. This way, the custom runtime is assured that the software thread is one-to-one with a physical core. It then implements a user-level thread package that lets it control which OS thread a computational task is assigned to. Finally, the runtime then implements the language's parallel semantics in terms of those user threads.

The user-level threading approach addresses the system overhead issue, but it still hides important events such as input-output or node-to-node communications in a cluster. Hence, the more scalable runtimes need to coordinate task assignment to cores with application access of input and output, memory allocation over non-uniform cache and memory hierarchies, offloading to hardware accelerators, power management, and inter-node communication in a cluster. The user-level threading approach also makes the parallel runtime implementation cumbersome, error-prone and complex, because it is still written in terms of threads.

Overall, parallel language implementations must deal with a number of challenges normally deferred to the operating system, and they still suffer from the complexity of non-blocking shared memory concurrency.

Ideally, the OS would be in terms of a mutable hardware abstraction, and export mutations as new behavior. We define a mutable hardware abstraction to be an interface to hardware-level behaviors that are normally inside the OS or below it. Examples include communication between cores, allotting time-slots to applications, and establishing ordering of events among cores (which is what atomic memory operations and equivalent patterns of instructions do). The kernel itself would be implemented in terms of such an abstraction, and would accept mutations the same way it accepts device-drivers. It would then export the mutated behaviors for the language to trigger.

A language would implement its runtime behaviors in the form of a mutation. Being inside the OS, such a runtime has secure access to kernel-only hardware mechanisms as well as the hardware abstraction. It could negotiate with the kernel to manage physical resources, in a low-overhead way. One benefit of this arrangement is that the language runtime gains the ability to control which task is assigned to which processing element at what time. This enables high performance and low-energy data affinity techniques. For example, the runtime could track data within the memory hierarchy and assign tasks to locations close to their consumed data.

Contribution. We show in this paper the definition and implementation of such a mutable hardware abstraction, albeit at user-level rather than in the kernel. The abstraction lets a language's runtime be implemented as a mutation, which we call a plugin. The plugin implements parallelism constructs and assignment of tasks to cores.

We focus in this introductory paper on the definition of the abstraction and its support for parallelism constructs, postponing exploration of assignment of tasks onto cores and other performance optimizations to following papers. This paper defines multiple time-lines in a program, and a virtual timeline that globally orders events from them. It demonstrates three sets of parallelism constructs: synchronous send-receive motivated by process calculi; spawn and sync from Cilk [START_REF] Frigo | The implementation of the cilk-5 multithreaded language[END_REF][START_REF]Cilk group at MIT[END_REF]; and mutex and condition variable from pthreads. The assignment policy we implemented with them is simply first-come first-served.

We call the abstraction Virtualized Master-Slave, or VMS. It exports facilities to create virtual processors and control how their timelines relate to each other, and relate to physical time. It also exports facilities to suspend a virtual processor and for an executable to interact with the plugin. The plugin embodies most of a language's runtime. A wrapper-library or keyword is what appears in application code, and is what triggers the runtime.

Organization of paper. Section 3 provide the original concepts and definitions of VMS. Section 4 focuses on the implementation, describing the elements and how they interact, then relating them back to the theoretical definition. Section 5 takes the point of view of the application code, studying the usage and implementation of parallel language constructs as a VMS plugin. To wrap up, measurements of effectiveness appear in Section 6 and conclusions in Section 7.

Background and Related Work

User-level thread packages and most parallel language runtimes have to side-step OS threads, by pinning one to each core, which effectively gives the user-level package control over the core. Our VMS implementation also does this. We are not claiming in this paper to have the OS level implementation of VMS that is possible -but just the user-space version.

Related work. The most primitive methods for establishing ordering among cores or distributed processors are atomic instructions and clock-synchronization techniques that time-stamp events [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF][START_REF] Christian | Probabilistic clock synchronization[END_REF].

Meanwhile, the most closely related work is Scheduler Activations [START_REF] Anderson | Scheduler activations: effective kernel support for the user-level management of parallelism[END_REF], which also allows modifying concurrency constructs and controlling assignment of virtual processors onto cores. However it has no virtual time to guarantee globally consistent sequentialization, and no interface for plugins. BOM [START_REF] Fluet | Manticore: a heterogeneous parallel language[END_REF], which is used in Manticore to express scheduling policies and synchronization, also bears resemblances to VMS, but at a higher level of abstraction. BOM is a functional language, rather than a primitive abstraction meant to sit at the hardware-software boundary as VMS is.

Coroutines is a high-performance means of switching between tasks. Coroutine scheduling and stack handling techniques were well suited to the user-space implementation of VMS.

Other related work either provides an abstraction of the thread model, or is a full language with specific parallelism constructs. As a protypic example of user-level threads, Cilk [START_REF] Frigo | The implementation of the cilk-5 multithreaded language[END_REF][START_REF]Cilk group at MIT[END_REF] provides a simplified abstraction with an efficient scheduling and load balancing algorithm, but limited to forkjoin concurrency. OpenMP [START_REF]OpenMP organization[END_REF] is a typical example of a parallel extension of sequential languages; it allows creating tasks and controlling their execution order. We claim that both Cilk and OpenMP, as well as most thread abstractions or parallel languages may be implemented via plugins to VMS, with similar performance.

VMS is unique in that it doesn't impose its own concurrency semantics as a programming model, but rather takes preferred ones as plugins. This makes it only a support mechanism to implement language runtimes -VMS is hidden from the application, underneath the language. Parallelism constructs may be implemented as VMS plugins, easily, quickly, and with high performance as indicated in Section 6.

This work presents a first incarnation and evaluation of VMS. We plan to explore the embedding into VMS of a variety of parallel languages, with a special interest for coordination languages [START_REF] Gelernter | Generative communication in Linda[END_REF][START_REF] Knobe | Ease of use with concurrent collections (CnC)[END_REF]5]. We will also explore VMS's compatibility with different concurrent semantics [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF][START_REF] Hoare | Communicating sequential processes[END_REF][START_REF] Milner | Communicating and Mobile Systems: The pi-Calculus[END_REF][START_REF] Hewitt | Actor model of computation[END_REF][START_REF] Agha | A foundation for actor computation[END_REF]. One particularly important application would be to use VMS to facilitate the design and implementation of the emerging hybrid programming models, such as MPI+OpenMP, or OpenMP+OpenCL [START_REF] Carribault | Enabling low-overhead hybrid MPI/OpenMP parallelism with MPC[END_REF][START_REF] Group | Open Compute Language homepage[END_REF].

Abstract Definition of VMS

We start with an intuitive overview, then precise the definitions and properties in the following sub-sections.

Definitions: 1) We want to avoid the confusion associated with the various interpretations for the terms "thread" and "task" so will use the term Virtual Processor (VP), which we define as state in combination with the ability to animate code or an additional level of virtual processors. The state consists of a program counter, a stack with its contents, a pointer to top of stack, and a pointer to the current stack frame. 2) A physical processor executes a sequential stream of instructions. 3) A program-timeline is the sequence of instructions animated by a Slave VP, which is in turn animated by a physical processor.

Intuitive Overview. VMS can be understood via an analogy with atomic instructions, such as Compare and Swap (CAS). These are used to establish an ordering among the timelines of cores. They consist of two parts: 1) the semantics of what is done to the memory location, 2) a mechanism that establishes an ordering among the cores. For CAS, the semantics are: "compare value in this register to value at the address, and if same, then put value in second register into the address." Multiple kinds of atomic instructions share the same order-establishing mechanism, they simply provide different semantics as a front-end.

VMS can be viewed as virtualizing the order-establishing mechanism. It allows the semantics to be plugged-in to it. This breaks concurrency constructs into two parts: the VMS mechanism, which establishes an ordering between events in different timelines; and the plugin, which supplies the semantics.

Below the interface, hardware mechanisms are employed to order specific points in one physical processor's timeline relative to specific points in another's timeline. Above the interface, a plugin provides the semantics that an application uses to invoke creation of the ordering.

Together, VMS plus the plugin form a parallelism construct, by which an application controls how the time-lines of its virtual processors relate. Such constructs also guarantee relations of VP time-lines to hardware events.

As an example, consider a program where one VP writes into a data structure then calls a send construct. Meanwhile, a different VP calls the receive construct then reads the data structure. The semantics of the send and receive constructs are that all data written before the send is readable in the other time-line after the receive. To implement these constructs, VMS provides the mechanism to enforce the ordering, and to include the writes and reads in that ordering. The plugin directs that mechanism to order the send event before the receive event.

What the VMS interface provides:

The interface provides primitive operations to create and suspend VPs; a way for plugins to control when and where each VP is (re)started; a way for application code to send requests to the plugin; and a way to order a specific point in one VP time-line relative to a specific point in another VP time-line. All implementations of the VMS interface provide these, whether it is on shared memory or distributed, with strong memory consistency or weak.

Specification in three parts. We specify the observable behavior of a VMS system with plugins present. Hence, the specified behaviors remain valid with any parallelism construct implementable with VMS. First we give the specification of a computation system that VMS is compatible with; then specify a notion of time and the key VMS guarantee; and lastly specify virtual processor scheduling states and transitions between them.

The Specifications for a VMS-compatible Computation System

-An application creates multiple VPs, which are Slaves, each with an independent time-line.

-A schedule of Slaves is generated by a Master entity, from within a hidden time-line(s).

-A schedule is the set of physical locations and time-points at which Slaves are (re)animated.

-All semantic parallelism behavior is invoked by Slaves communicating with the Master.

-A Slave communicates with the Master by using a VMS primitive, which suspends the Slave.

Where we define: Semantic Parallelism Behavior is the actions taken by a parallelism construct, which establishes an ordering among events in different Slave timelines.

Discussion:

The key point is that scheduling is separated from the application code. This is enforced by the schedule being generated in a time-line hidden from the application. The rest of the requirements are consequences of that separation.

The Master entity appears as a single entity, to the slaves. However it may be implemented with multiple (hidden) timelines. This is the approach taken in our initial implementation, which has several Master VPs hidden inside the VMS implementation.

The Time-Related Specifications of VMS

To prepare for the time-related specifications, we give an advance peek of the following section, 3.3. There, Slave VPs are specified to have three scheduling states: Animated, Blocked, and Ready. When a parallelism construct starts execution, the Slave transitions from Animated to Blocked. When it ends execution, the Slave transitions from Blocked to Ready. VMS provides a way to control the order of these state-transitions, which is equivalent to controlling the order of the parallelism-constructs. Controlling the state transitions is how the ordering among constructs in different timelines is established.

With that background, here are time-related specifications for VMS:

-VMS provides a Virtual timeline that globally orders changes of scheduling state of Slave VPs.

-Ordering is created among construct-invocations by controlling the order of Blocked to Ready transitions in the Virtual timeline. -Causally tied construct-invocations are tied-together inside the Master.

-VMS enforces ordering of observations of physical events in Slave timelines to be consistent with the Virtual time ordering. -Virtual time defines only ordering, but not spans, nor widths.

Discussion: Most importantly here, Virtual time defines a global ordering among Slave statetransitions. To make this useful for parallelism, VMS must be implemented so that observations of physical events, like reads and writes to shared memory, are consistent with that ordering.

The Virtual timeline plays the same role as the mechanism added to memory systems to support atomic instructions. All atomic instructions require hardware that establishes an ordering among the timelines of physical cores. That hardware sequentializes execution of atomic memory accesses to the same address. VMS virtualizes this mechanism. It provides the same ordering function.

An important point is that the Virtual timeline is generated inside the Master. When a Slave uses the VMS primitive to send a parallelism-construct request, it suspends. However, that Slave doesn't actually transition state from Animated to Blocked until the Master acknowledges the suspension. It is the acknowledgement that adds the Slave transition into the Virtual timeline.

The essential value of VMS is using it to control the order of observing events. It has to be able to causally link the execution of a parallelism construct in one timeline to the execution of a construct in a different timeline. Establishing such a causal link is called tying together two construct executions. It is specific executions from different timelines that are causally linked with such a tie.

The key VMS guarantee: the order of observing physical events is consistent with the order of tied together parallelism constructs.

To explain this, take as given: two Slaves both execute parallelism constructs, those are tied together by the Master, establishing a causal ordering from one to the other. So, one construct is the before-construct, the other is the after -construct. Now, the guarantee means that any events triggered before the before-construct, in its timeline, are guaranteed to be detected in the other timeline as also preceding the after-construct. In addition, events triggered after the after-construct are guaranteed not visible before the before-construct in its timeline. This two-part guarantee is the result of the above specifications of VMS's time-related behavior.

Definitions: Some more definitions, to prepare for the next explanation. 1) An ordering-point exists in a Slave VP's timeline as a zero-width event that can be tied to ordering points in other timelines. It is initiated by a Slave VP executing the suspend primitive, and ended by the Master transitioning the Slave back to Animated. 2) A trace-segment is a portion of a Slave VP's stream of instructions bounded by ordering-points.

Hence, the timeline of a Slave is a sequence of trace-segments. Each trace-segment is animated by a single physical processor, but not necessarily the same as animated the Slave's other trace segments. Relating time-lines to each other. Figure 1 shows two ordering points being tied together. A trace segment starts when an ordering-point is ended by its Slave transitioning to Animated. Because the transition to Animated exists as a point in Virtual time, the start of a trace-segment has a welldefined position within Virtual time. Likewise, a trace-segment is ended by its Slave executing the suspend primitive of VMS. Although this does not have a well-defined point in Virtual time, every execution of suspend is acknowledged by the Master, which transitions the Slave to Blocked. That transition does have a well-defined position in Virtual time. Hence, the end of every trace-segment is associated with a well-defined position in Virtual time.

As a result, trace segments can be ordered relative to each other, by checking their start and end points in Virtual time. If they have no overlap in virtual time then they have a total ordering. However, if any portion of them overlaps in Virtual time, then they are considered concurrent trace-segments, and their Slaves are considered to be executing in parallel between those points of Virtual time.

Note that this is conservative because it doesn't take into account the physical wait time between a Slave suspending and the Master acknowledging. The Slave may stop executing at a physical time-point that would map onto an earlier point in Virtual time. In some cases, ending the Slave's trace-segment at the earlier point would eliminate the overlap with a particular other trace-segment. But VMS's set of specifications doesn't allow such mapping of suspend-execution onto Virtual time (for implementation-related reasons, which require downloading the code and gaining experience with it, to establish a common language, for an explanation to be understood).

A subtlety is that events triggered before one tied ordering-point, might be visible in the other timeline before the other tied ordering-point. In the figure, segment 2.1 might be able to see events from segment 1.1 if it looked. The VMS guarantee doesn't cover overlapped trace-segments. Physical events triggered before are only guaranteed visible after the tie point, and events after are only guaranteed not visible before the tie point.

We call this bounded non-determinism, because events within overlapped trace-segments have non-deterministic ordering, but the region of non-determinism can be bounded by tied orderingpoints. This allows a program to specify non-determinism, but control the region of non-deterministic behavior. For example, a reduction construct could be created that non-deterministically assigns portions of the reduction work to overlapped Slave segments. It would tie together ordering points from all the Slaves that mark the end of reduction. Hence, the outcome is deterministic, but the path to get there is not.

Sequential algorithms for parallel constructs. The globally-consistent sequential order in Virtual time enables one of VMS's main benefits: sequential algorithms for parallel constructs. An implementation to tie ordering points together equals an implementation of parallel constructs. A plugin has an ordering of state transitions available, and chooses from those. Sequential algorithms rely on an ordering existing, while concurrent algorithms must include operations that establish an ordering. Plugins have Virtual time ordering available, so they can use sequential algorithms.

Specification of Scheduling State

Scheduling state is used in VMS to organize internal activity, for enforcing the guarantees.

-VPs have three scheduling states: Animated, Blocked, Ready; see Figure 2 Some important points: (1) only VPs Animated can trigger physical events that are seen in other program time-lines; (2) the distinction between Blocked vs Stalled is that a Slave has to explicitly execute a VMS primitive operation to enter Blocked. In contrast, Stalled happens invisibly, with no effect on semantic behavior. It is due to hardware events hidden inside VMS, such as interrupts.

The Ready state is used to separate the parallelism-construct behavior from the scheduling behavior. It acts as a "staging area" for scheduling. VPs placed into this state are ready to be animated, but the scheduler decides when and where.

An interesting point is that in VMS, the causal tie between timelines is created by actions outside program timelines. In contrast, memory-based lock algorithms place the concurrency-related behavior inside program timelines.

Transition Between Slave Scheduling States.

-VPs transition states as shown in Figure 2.

-Animated→Blocked is requested by a Slave executing suspend, but takes place in Virtual time at the point the Master acknowledges that request. -Blocked→Ready is determined by the semantics implemented in the plugin.

-Ready→Animated is determined by the scheduler in the plugin.

-Transitions in scheduling state have a globally consistent order in Virtual time.

The parallelism primitives executed by a program do not directly control change in scheduling states. Rather they communicate messages to the Master, via a VMS supplied primitive. If it suspended when sending the request, then the act of the Master acknowledging the request places the Animated→Blocked transition into Virtual time. Inside the Master, the plugin then processes the message. Based on contents, it performs changes in state from Blocked→Ready, creates new VPs, and dissipates existing VPs. Most communication from Slave to Master requires the Slave to suspend when it sends the message. A few messages, like creating new Slave may be sent without suspending.

The suspend primitive decouples local physical time from Virtual time. Execution causes immediate transition to Stalled in physical time, later the Master performs Animated→Blocked, fixing that transition in Virtual time. The only relationship is causality. This weak relation is what allows suspension-points to be serialized in Virtual time, which in turn is what allows using sequential algorithms to implement parallelism constructs.

Plugins

The Master entity has two parts, a generic core part and a plugin (Figure 3). The core part of the Master is implemented as part of VMS itself. The plugin supplies two functions: the communicationhandler and the scheduler, both having a standard prototype. The communication-handler implements the parallelism constructs, while scheduler assigns VPs to cores.

An instance of a plugin is created as part of initializing an application, and the instance holds the semantic and scheduling state for that run of the application. This state, combined with the virtual processor states of the slaves created during that application run, represents progress of the work of the application. For example, multi-tasking is performed simply by the Master switching among plugin instances when it has a resource to offer to a scheduler. The parallelism-semantic state holds all information needed to resume (hardware state, such as TLB and cache-tags is inside VMS).

Internal Workings of Our Implementation

We name the elements of our example implementation and describe their logical function, then relate them to the abstract model. We then step through the operation of the elements.

Elements and their logical function. As illustrated in Figure 4, our VMS implementation is organized around physical cores. Each core has its own master virtual-processor, masterVP, and a physicalcore controller, which communicate via a set of scheduling slots, schedSlot. The Master in the abstract definition is implemented by the multiple masterVPs plus a particular plugin instance with its shared parallelism-semantic state (seen at the top).

On a given core, only one of: the core-controller, masterVP, or a slave VP, is animated at any point in local physical time. Each masterVP animates the same function, called master loop, and each slave VP animates a function from the application, starting with the top-level function the slave is created with, and following its call sequence. The core controller is implemented here as a Linux pthread that runs the core loop function.

Switching between VPs is done by executing a VMS primitive that suspends the VP. This switches the physical core over to the controller, by jumping to the start of the core loop function, which chooses the next VP and switches to that (switching is detailed in Section 5 Figure 7).

Relation to abstract model. We chose to implement the Master entity of the model by a set of masterVPs, plus plugin functions and shared parallelism-semantic state. VMS consists of this implementation of the Master, plus the core-controllers, plus the VMS primitive libraries, for creating new VPs and dissipating existing VPs, suspending VPs, and communicating from slave VP to Master. In Figure 4, everything in green is part of VMS, while the plugin is in red, and application code appears as blue, inside the slave VP.

Virtual time in the model is implemented via a combination of four things: a masterLock (not shown) that guarantees non-overlap of masterVP trace-segments; the master loop which performs transition Animated→Blocked; the comm handler fn which performs Blocked→Ready and the scheduler fn which performs Ready→Animated. Each state transition is one step of Virtual time; is guaranteed sequential by the non-overlap of masterVP trace segments; and is global due to being in parallelism-semantic state that is shared (top of Figure 4).

Transitions Progressing⇄Stalled within the Animated state are invisible to the parallelism semantics, the Master, and Virtual time, and so have no effect on the elements seen. 1. master loop scans the scheduling slots to see which ones' slaves have suspended since the previous scan. 2. It hands these to the comm handler fn plugged in (which equals transition Animated→Blocked). 3. The VP has a request attached, and data in it causes the comm handler fn to manipulate data structures in the shared parallelism-semantic state. These structures hold all the slaves in the blocked state (code-level detail and example will come in Figure 8, Section 5). 4. Some requests cause slaves to be moved to a readyQ on one of the cores (Blocked→Ready). Which core's readyQ receives the slave is under plugin control, determined by a combination of request contents, semantic state and physical machine state. 5. During the scan, the master loop also looks for empty slots, and for each calls the scheduler fn plugged in. It chooses a slave from the readyQ on the core animating master loop. 6. The master loop then places the slave VP's pointer into the scheduling slot (Ready→Animated), making it available to the core loop. 7. When done with the scan, masterVP suspends, switching animation back to the core loop. 8. core loop takes slave VPs out of the slots. 9. Then core loop switches animation to these slave VPs. 10. When a slave self-suspends, animation returns to the core loop (detail in code in Figure 9), which picks another. 11. Until all slots are empty and the core loop switches animation to the masterVP.

Enabling sequential implementation of parallelism semantics. All these steps happen on each core separately, but we use a central masterLock to ensure that only one core's masterVP can be active at any time. This guarantees non-overlap of trace-segments from different masterVPs, allowing the plugins to use sequential algorithms, without a performance penalty, as verified in Section 6.

Relating this to the abstract model: the parallelism-semantic behavior of the Master is implemented by the communication handler, in the plugin. It thus runs in the Master time referred to, in the model, in Section 3. Requests are sent to the Master by self-suspension of the slaves, but sit idle until the other slaves in the scheduling slots have also run. This is the passive behavior of requests that was noted in Section 3, which allows the masterVPs to remain suspended until needed. This in turn enables the masterVPs from different cores to be non-overlapped. It is the non-overlap that enables the algorithms for the parallelism semantics to be sequential.

Code Example

To relate the abstract model and the internal elements to application code and parallelism-library code, we give code snippets that illustrate key features. We start with the application then work down through the sequence of calls, to the plugin, using our SSR [START_REF] Halle | VMS home page[END_REF] parallelism-library as an example.

In general, applications are either written in terms of a parallel language that has its own syntax, or a base language with a parallelism library, which is often called an embedded language. Our demonstrators, VCilk [START_REF] Halle | VMS home page[END_REF], Vthread, and SSR, are all parallelism libraries. A parallel language would follow the standard practice of performing source-to-source transform, from custom syntax into C plus parallelism-library calls.

SSR. SSR stands for Synchronous Send-Receive, and details of its calls and internal implementation will be given throughout this section. It has two types of construct. The first, called from-to has two calls: SSR send from to and SSR receive from to, both of which specify the sending VP as well as the receiving VP. The other, called of-type also has two calls: SSR send of type to and SSR receive of type, which allow a receiver to accept from anonymous senders, but select according to type of message. Application view. Figure 5 shows snippets of application code, which use the SSR parallelism library. The most important feature is that all calls take a pointer to the VP that is animating the call. This is seen at the top of the figure where slave VP creation takes a pointer to the VP asking for creation. Below that is the standard prototype for top level functions, showing that the function receives a pointer to the VP it is the top level function for.

The pointer is placed on the stack by VMS when it creates the VP, and is the means by which the application comes into possession of the pointer. This animating VP is passed to all library calls made from there. For example, the bottom shows a pointer to the animating VP placed in the position of sender in the send construct call. Correspondingly, for the receive construct, the position of receiving VP is filled by the VP animating the call.

Relating these to the internal elements of our implementation, the animatingVP suspends inside each of these calls, passing a request (generated in the library) to one of the masterVPs. The masterVP then calls the comm-handler plugin, and so on, as described in Section 4.

For the SSR create processor call, the comm-handler in turn calls a VMS primitive to perform the creation. The primitive places a pointer to the newly created VP onto its stack, so that when top VP fn is later animated, it sees the VP-pointer as a parameter passed to it. All application code is either such a top-level function, or has one at the root of the call-stack.

The send and receive calls both suspend their animating VP. When both have been called, the communication handler pairs them up and resumes both. This ties time-lines together, invoking the VMS guarantee. Both application-functions know, because of the VMS guarantee (Section 3), that writes to shared variables made before the send call by the sender are visible to the receiver after the receive call. This is the programmer's view of tying together the local time-lines of two different VPs, as defined in Section 3.

Concurrency-library view.

A parallelism library function, in general, only creates a request, sends it, and returns, as seen below. To send a request, it uses the combined request-and-suspend VMS primitive that attaches the request then suspends the VP. The primitive requires the pointer to the VP, to attach the request and to suspend it.

In Figure 6, notice that the request's data is on the stack of the virtual processor that's animating the call, which is the receiveVP. The VMS send sem request suspends this VP, which changes the physical core's stack pointer to a different stack. So the request data is guaranteed to remain undisturbed while the VP is suspended.

Figure 7 shows the implementation of the VMS suspend primitive. As seen in Figure 4, suspending the receiveVP involves switching to the core loop. In our implementation, this is done by switching to the stack of the pthread pinned to the physical core and then jumping to the start-point of core loop.

This code uses standard techniques commonly employed in co-routine implementations. Tuning effort spent in core loop is inherited by all applications.

Plugin view. SSR's communication handler dispatches on the reqType field of the request data, as set by the SSR receive from to code. It calls the handler code in Figure 8. This constructs a hash-key, by concatenating the from-VP's pointer with the to-VP's pointer. Then it looks-up that key in the hash-table that SSR uses to match sends with receives, which is in the shared semantic state seen at the top of Figure 4 in Section 4.

The most important feature in Figure 8 is that both send and receive will construct the same key, so will find the same hash entry. Whichever request is handled first in Virtual time will see the We implemented blocked dense matrix multiplication with right sub-matrices copied to transposed form, and ran it on a 4-core Core2Quad 2.4Ghz processor.

Implementation-time.

As shown in Table 1, time to implement the three parallel libraries averages 2 days each. As an example of productivity, adding nested transactions, parallel singleton, and atomic function-execution to SSR required a single afternoon, totaling less than 100 lines of C code.

Execution Performance. Performance of VMS is seen in Table 2. The code is not optimized, but rather written to be easy to understand and modify. The majority of the plugin time is lost to cache misses because the shared parallelism-semantic state moves between cores on a majority of accesses. Acquisition of the master lock is slow due to the hardware implementing the CAS instruction.

Existing techniques may improve performance, such as localizing semantic data to cores, splitting malloc across the cores, pre-allocating slabs that are recycled, and pre-fetching. However, in many cases, several hundred nano-seconds per task is as optimal as the applications can benefit from. 3. On left, time in seconds for MM. To the right, overhead for pthread vs. Vthread. First column: cycles for perfect memory. Second: total measured cycles. pthread cycles are from round-trip experiments.

Head to head. We compare our implementation of the spawn and sync constructs against Cilk 5.4, on the top in Table 3, which shows that the same application code has similar performance. For large matrices, Cilk 5.4's better use of the memory hierarchy (the workstealing algorithm) achieves 23% better performance. However, for small matrices, VCilk is better, with a factor 2 lower overhead. Cilk 5.4 does not allow controlling the number of spawn events it actually executes, and chooses to run smaller matrices sequentially, limiting our comparison.

When comparing to pthreads, our VMS based implementation has more than an order of magnitude better overhead per invocation of mutex or condition variable functionality, as seen on the bottom of Table 3. Applications that inherently have short trace segments will synchronize often and benefit the most from Vthread.

Conclusion

We have shown an alternative to the thread model that enables easier-to-use parallelism constructs by splitting the scheduler open, to accept new parallelism constructs in the form of plugins. This gives the language control over assigning virtual processors to physical cores, for performance, debugging, and flexibility benefits. Parallelism constructs of programming languages can be implemented using sequential algorithms, within a matter of days, while maintaining low run-time overhead.

Fig. 1 .

 1 Fig. 1. Time Behaviors: Shows Ordering Point 1.1 being tied to Ordering Point 2.1. As a result, VMS guarantees that events triggered in Trace Segment 1.1 are seen as having taken place in the past in Trace Segment 2.2. Also shows that there is no common tied ordering point between segments 1.2 and 2.2, so VMS provides no guarantees about what order segment 2.2 sees events triggered in segment 1.2.

  . -VPs in Animated are allowed to advance Program time with (core-local) physical time. -VPs in Blocked and Ready do not advance their Program time. -Animated has two physical states: Progressing and Stalled. -VPs in Progressing advance Program time with (core-local) physical time, those in Stalled do not (allowing non-semantic suspend for hardware interrupts). -Scheduling states are defined in Virtual time only. -Progressing and Stalled are defined in (core-local) physical time only; the distinction is invisible in Virtual time.

Fig. 2 .

 2 Fig. 2. Scheduling states of a slave VP in the VMS model. Animated, Blocked, and Ready are only defined in Virtual Time and only visible in the Master. Progressing and Stalled are only visible in physical-processor local time, not visible in Virtual time.

Fig. 3 .

 3 Fig.3. The Master, split into a generic core and a language-specific plugin. The core encapsulates the hardware and remains the same across applications. The plugin implements the semantics of the parallelism-constructs.

Fig. 4 .

 4 Fig. 4. Internal elements of our example VMS implementation

Fig. 5 .

 5 Fig.5. Application code snippets showing that all calls to the parallelism library take the VP animating that call as a parameter.

Table 1 .

 1 Person-days to design, code, and test each parallelism library. L.O.C. is lines of (original) C code, excluding libraries and comments.

				comp only comp + mem
		VMS Only master loop	91	110
	SSR Vthread VCilk Design 4 1 0.5 Code 2 0.5 0.5 Test 1 0.5 0.5 L.O.C. 470 290 310	Language: SSR	switch VPs (malloc) (create VP) plugin -concur plugin -all	77 160 540 190 530	130 2300 3800 540 2200
			lock		250
		Vthread plugin -concur	66	710
			plugin -all	180	1500
			lock		250
		VCilk	plugin -concur	65	260
			plugin -all	330	1800
			lock		250

Table 2 .

 2 Cycles of overhead, per scheduled slave. "comp only" is perfect memory, "comp + mem" is actual cycles. "Plugin-concur" only concurrency requests, "plugin-all" includes create and malloc requests. Two significant digits due to variability.

	Matrix size Lang. sec.
	81 × 81	Cilk 0.017
		VCilk 0.008
	324 × 324 Cilk	0.13	operation	Vthread	pthread ratio
		VCilk 0.13		comp only total
	648 × 648 Cilk	0.71	mutex lock	85 1050 50,000 48:1
		VCilk 0.85	mutex unlock	85 610 45,000 74:1
	1296 × 1296 Cilk	4.8	cond wait	85 850 60,000 71:1
		VCilk 6.2	cond signal	90 650 60,000 92:1
	Table

Acknowledgments This work was partly funded by the European FP7 project TERAFLUX.

return; } Fig. 7. Implementation of VMS suspend processor. Re-animating the virtual processor reverses this sequence. It saves the core loop's resume instr-addr and stack ptr into the VP structure, then loads the VP's stack ptr and jmps to its resumeInstrAddr. handle_receive_from_to( VirtProcr *requestingVP, SSRSemReq *reqData, SSRSemEnv *semEnv ) { commHashTbl = semEnv->communicatingVPHashTable; key[0] = reqData->receiveVP; key [START_REF] Agha | A foundation for actor computation[END_REF] = reqData->sendVP; //send uses same key waitingReqData = lookup_and_remove( key, commHashTbl ); //get waiting request if( waitingReqData != NULL ) { resume_virt_procr( waitingReqData->sendVP ); resume_virt_procr( waitingReqData->receiveVP ); } else insert( key, reqData, commHashTbl ); //receive is first to arrive, make it wait } Fig. 8. Pseudo-code of communication-handler for receive from to request type. The semEnv is a pointer to the shared parallel semantic state seen at the top of Figure 4. hash entry empty, and save itself in that entry. The second to arrive sees the waiting request and then resumes both VPs, by putting them into their readyQs.

Access to the shared hash table can be considered private, as in a sequential algorithm. This is because our VMS-core implementation allows only one handler on one core to execute at any time.


Gwénolé Lecorvé

Guillaume Gravier

Pascale Sébillot

AUTOMATICALLY FINDING SEMANTICALLY CONSISTENT N-GRAMS TO ADD NEW WORDS IN LVCSR SYSTEMS

Keywords: Automatic speech recognition, vocabulary adaptation, natural language processing, language modeling

This paper presents a new method to automatically add n-grams containing out-of-vocabulary (OOV) words to a baseline language model (LM), where these n-grams are sought to be grammatically correct and to make sense according to the meaning of OOV words. First, this method consists in determining the word sequences, i.e., n-grams, in which the usage of a given OOV word is the most semantically consistent. Then, conditional probabilities of these n-grams have to be computed. To do this, semantic relations between words are used to assimilate each OOV word to several equivalent invocabulary words. Based on these last words, n-grams from the baseline LM are re-used to find the word sequences to be added and to compute their probabilities. After augmenting the vocabulary and launching a recognition process, experiments show that our method results in WER improvements which are comparable to those obtained using a state-of-the-art open vocabulary LM.

INTRODUCTION

Large vocabulary continuous speech recognition (LVCSR) systems rely on a static finite vocabulary, which defines the set of all recognizable words, and on a statistical language model (LM), which gathers vocabulary word sequence (n-gram) probabilities. Hence, when an out-of-vocabulary (OOV) word is pronounced in a spoken document, the system cannot correctly transcribe this word and typically generates a sequence of acoustically close shorter words instead, thus decreasing recognition accuracy. A solution to this wellknown problem is to adapt the vocabulary according to spoken documents to be transcribed. This vocabulary adaptation task can be seen as selecting new words to be added to the vocabulary before integrating these words into the system's components. This paper focuses on this last point while disregarding the new word selection problem.

Integrating an OOV word into a pre-existing system can be split into two tasks. On the one hand, it is necessary to augment the pronunciation dictionary by phonetizing the new word. This task can typically be achieved by using automatic grapheme-to-phoneme conversion tools. On the other hand, the new word has to be integrated into the system's language model in order to associate probabilities with transcript hypotheses containing the new word. To do this, a first approach consists in re-estimating the language model based on the augmented vocabulary, usually by interpolating counts or probabilities of n-grams containing the OOV word that have been directly observed from a general-purpose text corpus and from a small task-specific one [START_REF] Kemp | Reducing the OOV rate in broadcast news speech recognition[END_REF][START_REF] Martins | Dynamic vocabulary adaptation for a daily and real-time broadcast news transcription system[END_REF][START_REF] Yamazaki | Dynamic language model adaptation using presentation slides for lecture speech recognition[END_REF]. However, OOV words are often rare words-even in a task-specific corpus-, and this approach is not optimal because only a few n-grams related to each OOV word to be added can be observed and their probabilities cannot be reliably estimated. Thus, after adaptation, a new word still frequently tends not to be recognized by the system when decoding a speech signal. A second, state-of-the-art, approach relies on hybrid LMs which mix probabilities over words and lexical class sequences. In these LMs, referred as open vocabulary LMs, each OOV word is replaced by its lexical class when computing the probability of a sequence containing such a word. The main interest of this approach is then to avoid any n-gram probability re-estimation step when adaptating the vocabulary. However, an important drawback is that lexical classes are chosen based only on one criterion, e.g., the morphosyntactic information [START_REF] Allauzen | Open vocabulary ASR for audiovisual document indexation[END_REF][START_REF] Martins | Automatic estimation of language model parameters for unseen words using morpho-syntactic contextual information[END_REF] or some semantic aspects of OOV words [START_REF] Chung | A dynamic vocabulary spoken dialogue interface[END_REF]. Thus, the open vocabulary strategy disregards other linguistic features which could assist the system in discriminating OOV words of a same class while transcribing an utterance. Whereas named entities can typically be effectively accounted for by classes since they usually share common syntactic usages, other words are much more affected by this restriction of lexical classes since these words can be used in different specific ways depending on their various potential meanings. Hence, we will focus on OOV words aside named entities.

In this paper, we present a new method to automatically add n-grams containing OOV words to a baseline LM. This method is particularly original since it does not rely on any extra textual corpus where the OOV words could be found, and the n-grams added are sought to be semantically consistent, i.e., they have to make sense according to the meaning of OOV words. The proposed strategy first consists in determining the word sequences, i.e., n-grams, in which the usage of a given OOV word is the most semantically, as well as grammatically, consistent, and then in estimating conditional probabilities for these n-grams before integrating them into the baseline LM. To do this, semantic relations between words are used to assimilate each OOV word to several equivalent in-vocabulary (IV) words. Based on these IV words, n-grams from the baseline LM are re-used to find the word sequences to be added and to compute their probabilities.

This paper is organized as follows: our automatic scheme to find semantically consistent word sequences is exposed in Section 2 while Section 3 outlines how the probability of these sequences can be integrated into a pre-existing LM. Finally, Section 4 presents back-end experiments and compares the results of our method with those obtained using an open vocabulary LM.

FINDING CONSISTENT WORD SEQUENCES

The basic idea to find word sequences related to new words is that, within an utterance, some words can be replaced by some others without significantly changing the meaning of the utterance. For ex-ample, the utterances "the nightingales are singing" and "the owls are singing" are semantically close since they both rely on the fact that birds can sing. Based on this principle, word sequences related to an OOV word to be added can be determined by relying on equivalent IV word sequences. This section first presents a formal equivalence relation between words and between word sequences. Then, a score is proposed to select equivalent word sequences which tend to be the most substantiated for each OOV word. Finally, an instantiation of these two points is exposed through the use of paradigmatic relations.

Word and n-gram equivalence relations

Within natural language, the usage of a word in an utterance depends on various information. On the one hand, it depends on its meaning with respect to the other words. For example, the semantic information of a given noun may favor some adjectives or verbs to come along with, while it may also prevent from using other words. Hence, some words can be replaced by others without changing the global meaning of an utterance, whereas some other replacements are clearly inconsistent. On the other hand, since natural language is constrained by grammatical rules, the correct usage of a word depends on its morphosyntactic information, i.e., its grammatical category and its inflection.

Hence, each word w can be represented by its lemma1 w and its part-of-speech (POS) tag pw, and two words w and v can be considered as equivalent if their lemmas are linked according to a semantic relation R and if their POS tags are equal, i.e.,:

w ≡ v ⇔ w R v and pw = pv , (1)
where w R v means that w is linked to v according to R. By extension, two word sequences X and Y of length n are defined as equivalent if and only if:

X ≡ Y ⇔ ∃i ∈ [1..n], xi ≡ yi and ∀j = i, xj = yj , (2)
where xi and yi stand for the i-th word of X and Y respectively. Based on this equivalence principle, the goal is now to find out which sequences containing a new word have to be integrated into the baseline LM.

Selecting equivalent word sequences

Given an OOV word w, all the sequences AwB, where A and B are word sequences, are candidates to be integrated into the pre-existing LM. Since many of these possible sequences are irrelevant to the word w, a score S(AwB) is defined to only select the few most linguistically substantiated. This score evaluates the frequency of each equivalent sequence AvB within a set Ω of pre-existing word sequences, weighted by the strength r( w , v ) of the link between the lemmas of w and v according to a given semantic relation R. This can be formulated as follows:

Sn(AwB) = v st. w≡v r( w , v ) × |AvB|Ω , ( 3
)
where n is the length of AwB and |AvB|Ω stands for the number of times where AvB is observed in Ω. For each length n, the average value µn is computed based on all non-zero scores Sn(. each length n, only word sequences whose score is greater than µn are selected, whereas others are discarded. From a computational point of view, this whole scheme can efficiently be implemented using a sequencial scanning of Ω.

Instantiation through paradigmatic relations

In our experiments, the set of word sequences Ω is made of all the n-grams of the pre-existing LM 2 and R has been instantiated by paradigmatic relations between lemmas. These relations show which lemmas appear in same lexical environments, while they do not necessarily appear together within these environments [START_REF] Grefenstette | Corpus-derived first, second and thirdorder word affinities[END_REF]. Typically, this results in automatically linking a word with its synonyms, hypernyms, antonyms, etc. In our work, these relations have been trained automatically from French newspaper archives. For each lemma 1, a context vector is computed from this large text corpus by sliding a fixed-size window (20 words) along the whole text. This context vector gathers the frequencies of words appearing with 1 within a same window. Then, only the 10 lemmas 2 whose context vector results in the highest cosine measure with the context vector of 1 are considered as linked with 1. At the same time, this cosine value is defined as the strength r( 1, 2) of this link. Following this scheme, Table 1 lists a few automatically found word sequences for 3 sample OOV words, presented along with their semantically related lemmas. For understanding purposes, these examples have been translated from French into English. However, since French contains word inflection forms which do not exist in English, genders, numbers and tenses of original French OOV words are precised. From these examples, it clearly appears that the word sequences found by our technique make sense and are grammatically consistent. Hence, their use while decoding a speech signal should be worthwhile to transcribe OOV words. Thus, these sequences are now considered as new n-grams for which one has to compute conditional probabilities before integrating them into a baseline LM.

ASSIGNING PROBABILITIES

After finding semantically consistent n-grams for a new word, conditional probabilities must be computed in order to give a real existence to this word in a pre-existing LM. To do this, given a selected n-gram W , the joint probability P (W ) is first computed as:

P (W ) = V st. W ≡V P (V ) NW , (4)
where P (V ) is the joint probability of an equivalent n-gram V in the LM, and NW denotes the number of these equivalent n-grams.

Unfortunately, sometimes, no n-gram can be found for a given OOV word because the latter cannot be associated with any other word according to the automatically trained paradigmatic relations. In this case, only a unigram can be added to the LM. However, the probability of this unigram cannot be estimated as in (4). To circumvent this problem, a default unigram probability is empirically set to 10 -8 . Since this case is rather rare-this phenomenon only affects less than 20 % of our OOV words-, no specific attention has been paid to this probability. Hence, the default value used does not result from a tuning process. It only corresponds to a typical value for rare unigrams already listed in our back-end experiment LM. Then, using the Bayes law, conditional probabilities are computed, probability mass of modified LM histories are renormalized and backoff weights are rescored.

EXPERIMENTS AND RESULTS

Experiments are carried out on 3 hours of broadcast news shows coming from the French corpus ESTER [START_REF] Galliano | The ESTER phase II evaluation campaign for the rich transcription of French broadcast news[END_REF]. These shows are split into a development set and a test set. As it can be seen from statistics of Table 2, the number of OOV words in these sets is rather limited.

Hence, experiments presented in this section must be thought as still preliminary, and results should be carefully interpreted. Then, let us recall that only common words are considered while proper nouns have been discarded, hence the low OOV rates. For each dataset, remaining OOV words are added to the vocabulary and phonetized using the French grapheme-to-phoneme converter LIAPHON [START_REF] Béchet | LIA PHON : un système complet de phonétisation de textes[END_REF]. Assuming that the POS of the OOV words are known, new n-grams are found, their probabilities are computed and they are integrated into our 4-gram LM based on a 65K words vocabulary. A new transcript is finally generated.

To validate the performance of our vocabulary adaptation scheme, the WER of this new transcript is compared to results obtained using other strategies. First, oracle WERs have been computed. These rates correspond to the best theoretically obtainable WERs, i.e., assuming all considered OOV words are well recognized. Another strategy consists in limiting inserted n-grams to the sole unigrams. This corresponds to the most basic way of integrating new words into the baseline LM. Finally, our technique is also compared to the state-of-the-art open vocabulary LM strategy in which the probability of a new word woov given an history h is computed as:

P (woov|h) = P (coov|h) × P (woov|coov) , ( 5
)
where coov is the class of woov, and the term P (woov|coov) prevents from probability over-estimating for OOV words. In practice, a 4-gram LM based on 14 lexical classes corresponding to POS categories (verbs, nouns, adjectives, etc.) was built so that it results in the same baseline performances as those obtained using the closed vocabulary LM. Besides, the probability P (woov|coov) has been set to 10 -5 after optimizing the WER on the development set. The WERs measured using each of these strategies for the development and the test sets are presented in Table 3, where our method is referred by the label "N-grams". While the absolute oracle WER decrease is of 0.6, it first appears that using only unigrams already leads to an absolute gain of 0.3. This is not surprising since OOV words are usually long words, which makes them acoustically unambiguous and easily recognizable by the sole acoustic models. This case is illustrated by example #1 of Table 4. Second, it appears that our technique leads to an absolute WER decrease of 0.5 on the development set. This improvement is similar to the one returned by the open vocabulary LM. The same trends can be observed on the test set, though global improvements are a bit lower. Especially, our method still leads to the same improvement as when using an open vocabulary LM. This is all the more interesting since these absolute WER decreases of 0.3 are both statistically significant according to a paired t-test and to a Wilcoxon test 3 .

To evaluate the impact of the different strategies on added OOV words, WERs on these sole words have been measured. These rates, referred as WERoov, are presented in Table 5. On the one hand, as previously highlighted, it appears that using unigrams already results in correctly transcribing up to 50 % of all the OOV words. On the other hand, results show that the open vocabulary LM leads to more frequently correctly transcribe OOV words. However, after precisely analyzing the n-grams and the transcripts generated using our technique, it appears that these slightly worse WERoov results emanate from the absence of paradigmatic relations for some OOV words, thus leading to only consider unigrams. This problem could Example #1 Reference these are pan-islamist movements Baseline these are LOINCLOTH ISLAMIST movements Unigrams these are pan-islamist movements N-grams these are pan-islamist movements Open vocabulary these are pan-islamist movements Example #2 Reference dozens of women dressed in blue djellabas Baseline dozens of women dressed in blue DJELLABA Unigrams dozens of women dressed in blue DJELLABA N-grams dozens of women dressed in blue djellabas Open vocabulary dozens of women dressed in THE djellabas Table 5. WERs measured on the sole OOV words (WERoov) for the same set-ups as in Table 3.

probably be avoided by relying on additional relations between lemmas. Nonetheless, when opposed to the similar WERs previously reported in Table 3, these WERoov differences interestingly mean that, for each transcribed OOV word, our technique leads to more effectively transcribe its nearby words with respect to the open vocabulary LM. This point is illustrated by the example #2 of Table 4. By relying on paradigmatic relations, our technique associates the OOV word "djellabas" with other types of garment and, then, leads to add n-grams with adjectives refering to colors. This enables the system to produce the right transcription of the whole utterance, whereas the open vocabulary LM leads to correctly transcribe the word "djellabas" but it does not for the adjective "blue". Hence, our technique achieves a better integration of OOV words according to their meaning.

CONCLUSION AND FUTURE WORK

In this paper, we have proposed a new method to automatically find semantically consistent n-grams containing OOV words in order to add these n-grams into a baseline LM within a vocabulary adaptation process. This strategy relies on the use of semantic relations between lemmas in order to assimilate OOV words to equivalent invocabulary words. By instantiating this general scheme through the use of automatically learned paradigmatic relations, we have shown that it results in the same WER improvements as when using the state-of-the-art open vocabulary strategy. Moreover, while open vocabulary LMs tend to consider all the words of a same class as having a same semantic role, the merit of our approach is to achieve a better semantic integration of OOV words. This conclusion is all the more interesting since our method remains based on a closed vocabulary LM, as those used in most current LVCSR systems. Nonetheless, further improvement possibilities should be investigated. First, apart from paradigmatic relations, it could be interest-ing to rely on other relations between lemmas. Especially, it could be useful to consider relations between compounds and their constituent words. For example, an OOV word like "orthomyxovirus", for which no paradigmatic relation can easily be learned since this is a very rare word, could be automatically reduced to its simpler form "virus" by using word composition rules. Additionally, when only a few n-grams are automatically found, the relation R could be avoided so that the equivalence relation between words would rely on the sole morphosyntactic information. Hence, the integration of a minimum number of n-grams would be guaranteed for each OOV word. Then, further investigation should be done according to the integration of new n-gram probabilities into a pre-existing LM. Especially, future work should focus on the probability mass re-estimation problem of enriched LM histories in order to ensure the whole LM distribution not to degenerate when to many new n-grams are added. This is an arduous task since, when estimating the baseline LM, the probability masses are estimated through a complex process involving elaborate smoothing techniques. Finally, our strategy should be tested on a dataset with a larger number of OOV words. Similarly, it should be plugged with an automatic OOV word selection scheme in order to make the whole vocabulary adaptation process completely unsupervised. This could also be a good opportunity to assess the behavior of our technique when thousands of OOV words are added to the system.

Table 1 .

 1 ). Then, for OOV word: JAMAICAN French word: jamaïcaines (feminine, plural) Related lemmas: afro-american, mixed, pop, techno, west indian Found n-grams: jamaican musics, jamaican origins, jamaican and african, jamaican quarters, jamaican songs, his (her) jamaican roots, jamaican waters, jamaican and caribbean French word: garent (3 rd person, plural) Related lemmas: burn, crash, immobilize, station Found n-grams: park on the, park in front of the, park along, permanently park, they park, double park, who park, park their vehicle Examples of automatically found word sequences for 3 OOV words.

	OOV word: ONCOLOGISTS
	French word: cancérologues (masculine or feminine, plural)
	Related lemmas: biologist, cardiologist, doctor, lawyer, neu-
	rologist, paediatrician, psychiatrist, surgeon
	Found n-grams: oncologists who specialize in, oncologists
	from hospitals, many oncologists, american oncologists, for the
	oncologists, most oncologists, oncologists and doctors, accord-
	ing to oncologists
	OOV word: PARK (Verb)

Table 2 .

 2 Statistics on OOV words in the development set and in the test set.

	Development	Test

Table 3 .

 3 WERs measured on the development and on the test sets using a standard LM (Word only vocabulary) or using an open vocabulary LM (Word+class vocabulary). For both setups, baseline and oracle results are presented, as well as those obtained after augmenting the vocabulary. Considering the closed vocabulary LM, experiments have been carried out by considering only unigrams or by relying on automatically found n-grams. In parentheses, the absolute WER variation with respect to the baseline WER.

Table 4 .

 4 Comparison of 2 reference segments transcribed using different setups. These examples have been translated from French. Erroneous words are in uppercase, while OOV words are in bold.

			Development	Test
	Word only vocabulary	Initial vocabulary Unigrams N-grams	100 50 35	100 66 32
	Word+class	Initial vocabulary	100	100
	vocabulary	Augmented	21	21

A lemma is a canonical form of a word. For example, plural nouns are reduced to their singular form, conjugated verbs are reduced to their infinitive form, etc.

This represents an amount of about 5 millions 4-grams.

For our technique, p-values are of 2.7 × 10 -5 and 2.2 × 10 -5 for the paired t-test and for the Wilcoxon test, respectively, while they are of 1.7 × 10 -6 when using the open vocabulary LM. For each test, the confidence level α was set to 0.05.


Julien Lawto
email: julien.lawto@3ds.com

Jean-Luc Gauvain

Lori Lamel

Gregory Grefenstette

Guillaume Gravier

Julien Despres

Camille Guinaudeau

Pascale Sebillot

A SCALABLE VIDEO SEARCH ENGINE BASED ON AUDIO CONTENT INDEXING AND TOPIC SEGMENTATION

Keywords: Video indexing, Video search, Video Browsing

One important class of online videos is that of news broadcasts. Most news organisations provide near-immediate access to topical news broadcasts over the Internet, through RSS streams or podcasts. Until lately, technology has not made it possible for a user to automatically go to the smaller parts, within a longer broadcast, that might interest them. Recent advances in both speech recognition systems and natural language processing have led to a number of robust tools that allow us to provide users with quicker, more focussed access to relevant segments of one or more news broadcast videos. Here we present our new interface for browsing or searching news broadcasts (video/audio) that exploits these new language processing tools to (i) provide immediate access to topical passages within news broadcasts, (ii) browse news broadcasts by events as well as by people, places and organisations, (iii) perform cross lingual search of news broadcasts, (iv) search for news through a map interface, (v) browse news by trending topics, and (vi) see automatically-generated textual clues for news segments, before listening.

INTRODUCTION

Many of the major news organisations provide immediate access to topical news broadcasts over the internet, through RSS streams or podcasts. In parallel, many users rely on third-party sites 1 to describe topical extracts of longer news broadcasts. However, in spite of early attempts on broadcast news retrieval and browsing from speech [START_REF] Merlino | Broadcast news navigation using story segmentation[END_REF][START_REF] Maybury | Broadcast news navigator (bnn) demonstration[END_REF][START_REF] Hauptmann | Informedia at TRECVID 2003: Analyzing and searching broadcast news video[END_REF], technology has not made it possible for a user to efficiently find small segments of interest from longer broadcasts within a large collection spanning multiple languages. In particular, work on topic segmentation of broadcast news, e.g. [START_REF] Van Mulbregt | Segmentation of automatically transcribed broadcast news text[END_REF][START_REF] Allan | Topic detection and tracking: event-based information organization[END_REF] was limited in the number of shows and languages that could be handled. 1 For example, reddit.com, huffingtonpost.com, newser.com, ... Most current video search engines rely, in a large part, on indexing the textual metadata associated with the video (title, tags, surrounding page-text). Videos that are returned for a search over common search engines are those which contain those search terms in their metadata. Recent progress in spoken language processing (in transcription, topic segmentation, keyword extraction) has led to a number of robust tools that allow us to now provide users with quicker and more focussed access to relevant segments of one or more news broadcast videos. Researchers have focused on either one or the other aspect of the processing chain. For example, new approaches to topic segmentation of broadcast news have been proposed in [START_REF] Christensen | Maximum entropy segmentation of broadcast news[END_REF][START_REF] Liang | Program segmentation for tv videos[END_REF][START_REF] Guinaudeau | Improving asr-based topic segmentation of tv programs with confidence measures and semantic relations[END_REF], the latter focusing on robustness to different shows and to transcription errors. Still, few systems integrate all of these components in a complete and comprehensive large scale demonstration able to return portions of videos relevant to a query, while also providing query-free browsing capabilities. This paper presents a complete system demonstrating an alternative approach for browsing and searching videos and audio newscasts based on robust spoken document processing in multiple languages. In broadcast news, most of the linguistic information is encoded in the audio channel of video data, which, once transcribed, can be processed using natural language processing and semantic processing techniques. The interface presented here integrates many of these technologies to provide topical access to automatically identified broadcast segments. The main novelty here, with respect to similar available systems (including previous versions of our own) is the topical segmentation of news broadcasts. All the search and browsing tools are generated from automatically detected topic segments, using methods described below. Search is constrained to each segment, and these segments are returned as the result of a search, though the entire broadcast is still accessible, if desired. For example, if a user searches for Ron Paul AND Barack Obama, only those segments in which both politicians are mentioned will be returned. Our interface also provides additional, more elaborate optional annotations for each segment: named entities, timestamps of mentions of each query term, a pincushion timeline bar showing mentions, and for each segment, a label of corpus-derived important terms mentioned in that segment. Querying can be performed in a language different from broadcast language, exploiting commonly available translation tools. The paper is organized as follows: Back-end processing of the video and audio sources is described in Section 2. Section 3 describes the user interface, illustrating the various features of the system. In Section 4, processing time is discussed, followed by a conclusion and a description of future evolution of our system.

BACK END: OFF LINE PROCESSING

Our system indexes freely available podcast sources, broadcast via RSS streams. Figure 1 presents the main steps of the processing of these podcasts.

Automatic Speech Recognition (ASR)

State-of-the art speech transcription systems for 7 languages (French, English, Spanish, Mandarin, Dutch, Russian and Arabic) are the core of the demonstration. The transcription systems make use of statistical modelling techniques similar to those described in [START_REF] Jelinek | Continuous speech recognition by statistical methods[END_REF][START_REF] Gauvain | The LIMSI Broadcast News Transcription System[END_REF], which gives details for an English broadcast news system. The acoustic and language models and pronunciation dictionaries are language dependent [START_REF] Kirchhoff | Dictionaries for Multilingual Speech Processing[END_REF][START_REF] Lamel | Speech processing for audio indexing[END_REF], and trained on large audio and text corpora. Speech decoding is carried out in a single pass with statistical n-gram language models, and takes less time than the signal duration. Proper case is output for all languages, and postprocessing converts numerical quantities for amounts, dates, telephone numbers to Arabic numbers for English, French, and Spanish. The system outputs an xml file containing the words identified in the audio document, along with their time codes and a transcription confidence measure. Our first processing step partitions the data into speech segments, and, after determining the gender, clusters segments from the same speaker. This information can later be combined with the content in the automatic transcription to associate true speaker names to parts of the data. Each language has recognition word lists containing from 50k to 300k words which generally give a good coverage of the language. However, "breaking news" may have repeated occurrences of words that are unknown to the system. New functionality has recently been incorporated which allows users to update the recognition word list and this technology is currently undergoing experimentation. This automatic speech recognition technology used in our system has been frequently demonstrated to obtain top performance in international benchmarks.

Topic segmentation

A news broadcast is often divided into stories, which may have no relation with each other. If the broadcast is transcribed into one textual document, a complex search, such as Barack Obama in China, may return videos in which China is mentioned in one story and Barack Obama in another, contrary to what the user intended to find. To remedy this problem in the newest version of our system, we process the uninterrupted textual output of the automatic speech transcription by applying topic segmentation to break the transcript of a show into Topic segmentation has been studied in natural language processing since the early 1990s [START_REF] Hearst | Multi-paragraph segmentation of expository text[END_REF]. Most approaches use vocabulary differences in windows over the document to detect subject changes and topic shifts. Our system relies on an extension of the linear segmentation methods described in [START_REF] Utiyama | A statistical model for domain-independent text segmentation[END_REF]. The general idea of this lexical cohesion based method is to search for the best possible segmentation among all the possible ones. A generalized probability criterion is used to measure thematic cohesion of a segment, exploiting repetitions in the vocabulary: A unigram language model, estimated from the word counts in the segment, is used to compute the probability of the word sequence corresponding to the segment. Our language model estimation has been improved with respect to [START_REF] Utiyama | A statistical model for domain-independent text segmentation[END_REF]. We added features to account for the peculiarities of broadcast news transcripts, namely transcription errors and the limited number of repeated words due to stylistic reasons. In particular, word level confidence measures are used to deal with transcription errors while semantic relations are introduced to counteract the limited number of repetitions with the same methods as in [START_REF] Guinaudeau | Improving asr-based topic segmentation of tv programs with confidence measures and semantic relations[END_REF]. In practice, each word in the transcript is labelled with part-of-speech tags and lemmatized. Computation of thematic coherence probability is limited to nouns, adjectives and non-modal verbs. The output of the topic segmentation process is a set of segments. As a byproduct, that we exploit, each segment can be labelled by the few keywords which most significantly contributed to the lexical cohesion of the segment.

Index and semantic filters

Once speech is transcribed into text and segmented, standard natural language processing (NLP) techniques are applied to each segment. Extracted words, named entities (people, location, organization and events), and multi-word terms are then indexed, along with their time codes from the original automatic speech recognition, with a search engine. We use a proprietary NLP framework similar to the GATE and UIMA open source frameworks. It is resilient and scalable and has been built to scale to terabytes of input, typically an order of magnitude greater than the open source framework. It is able to efficiently process billions of words, and handle streams of hundreds of thousands of tokens per seconds. This NLP framework has been tested over several billion web pages.

BACK END: OFF LINE PROCESSING

Once video and audio streams have been segmented and processed, the user is presented with a welcome screen that shows trending people, places, locations, and events over a user definable period (day, week, months). This welcome screen allows users to keep abreast of the latest news, without formulating a query. The user can also search in the unique search box, as in classical search.

Index and semantic filters

The welcome page gives an overview of current news using tag clouds or chart pies, underneath a familiar search box. It presents named entities (people, location, organization and event) automatically extracted from all podcast news within a specified time period selected by the user on the time line. Figure 2 on the previous page shows two examples: if we select a period in August 2010, we can see that the event that appears the most is Ramadan. In the second example, the period is end of October and the main event is Halloween. Clicking on the word in the tagcloud or on a slice in the piechart executes a query over the broadcasts. A query can also be posed as in any classical search engine, with the user typing keywords in the search box. An autocompletion service is provided, helping to spell named entities known to the system. All advanced search functions are available, as with classic web search engines: matching exact phrases, logical and regular expressions. Lemmatization and the use of stop words are specific to the language selected by the user.

Result page thumbnails

In response to a query, we have provided a rich interface with multiple views on the results. In addition to thumbnails, timelines, and tag clouds views, the user now has access to a map view showing locations mentioned in fetched segments, as well as automatically determined trends in these segments. These maps and trends are all calculated from the ASR transcription of the audio streams of the broadcasts. Search is performed using a navigation look and feel that is familiar to search engine users. Figure 3 on the previous page illustrates these different views with the query "Afghanistan". The list view is the classic search engine results page, presenting a list of hits with text snippets related to the query. Thumbnails are contextual, drawn from time related to the text snippet. The user can launch the video at the exact time by clicking on the corresponding thumbnail. On the right of this screen, faceted search provides another mechanism for search and refinement using metadata (such as the source of the podcasts) or terms extracted from the broadcast content (such as named entities). Another view on the same data presents the results as large thumbnails with overlayed text snippets. By clicking on the next icon (the white arrow at eh bottom of the thumbnail) the user can scroll through the parts of the video when the query is mentioned, with appropriate thumbnails related to the moments when the words are mentioned. The map view (shown in the lower left of Figure 3) offers the possibility to see the locations mentioned, automatically extracted from the transcribed text. When clicking on the map on Iraq, for example, we can see the contextual snippets of the results set that correspond to the query Afghanistan with a refine on Iraq: both words are highlighted giving a quick overview of the context to the user. The trends view (lower right corner of Figure 3) sometimes provides a better visualization of the facets related to the query using charts or tag cloud. In all the views, a histogram time-line allows users to restrict the search to a specific time period. It also allows the user to visualize the number of times that the query term has been mentioned over time.

Segment browsing

Once a query result has been selected, the corresponding video is streamed, starting directly from the segment relevant to the query. The timeline of the video player presents markers with snippets of 30 words containing the query-relevant keywords corresponding to moments where the query words are mentioned. As illustrated in Figure 4, where the query was Tony Curtis, we see ont he timeline that the last segment of this CBS news broadcasts is the targeted segment that deals with Tony Curtis.

On the same page, we can see that other segments are presented. A thin white progression line shows the position of the current play within the whole video. When the user positions the cursor on a segment bar, we show keywords that are mentioned in this segment (shown here as white text in a black box). Associated to these keywords, the named entities that correspond only to the segment are displayed on the right of the video player. These labels and named entities highlight the topics that are discussed in the segment 2 .

Figure 5 shows some of the other segments in the same broadcast. In the first segment, extracted keywords shown as white text in black boxes (too small to read here) are "storm", "Carolina" and the named entities related are "Carolina beach", "New Jersey". The report was about a storm on the East Coast of the US, and that the automatically chosen labels were relevant in this case. In the second case the keywords were "foreclosure", "home" and "year"; "year" is obviously too generic but "foreclosure" describes the main subject of that segment.

Cross-language search

Another feature we implemented for searching and browsing videos is cross lingual information retrieval, i.e., querying in one language and see the results from other languages. In figure 6, a query Afghanistan is posed in English (as illustrated by the flag). By clicking on the search in other languages, the application uses external translation services to translate the query and display the results in the selected language (Arabic, in the example). The results are displayed in Arabic but can also be translated in English: the snippets and the facets are translated but can still be clicked to play the podcast. The play page can also be translated as a whole, therefore, the search can be in other languages and displayed in any language in an easy and intuitive way for the user.

PERFORMANCE

Two servers are used in this demonstrator. The first one is for the back-end fetching and indexing, in form of a distributed task scheduler. 2 The named entities extracted from this segment are all related to the query: Bernie Schwartz is his real name, Jamie Lee Curtis is his daughter and Marilyn Monroe and Jack Lemmon starred with him in Some Like It Hot.

Figure 4 Video output page with segmentation

Our system is built around a highly robust and distributed task queue, with replaceable workers, as in any map reduce system. Each task is scheduled on a worker (multiple workers per machine) by the queue manager and executed. Workers can be removed or added without any task being lost. The system processes more than 150 new video and audio items each day, amounting to roughly 3.5 Gb or 15 hours of new daily content, on a single 6 core server. Potentially, this server could ingest and process about 100 hours of videos per day. As this backend is fully distributed, servers can be immediately added in the system to handle any load. Another easily parallizable server is dedicated to handling user queries, able to handle 500 unique visitors per day. This configuration is highly scalable and is very similar to our commercial website exalead.com/search (which holds 16 billion web pages). Voxalead currently contains more than 70,000 podcasts.

CONCLUSION AND NEXT STEPS

Here we described our system for searching and browsing news videos by their language content. We provide many complementary ways to access video and audio content, but the main novelty of our system is that video content is not presented as a single block, but is segmented by its content, and accessible in query-dependent segments. Podcast content is currently derived essentially from the audio part however, the planned next steps are to augment this content via deeper image processing tools like OCR and face recognition. We are also considering adding speaker recognition for the next version.

Figure 1

 1 Figure 1 Overview of the architecture of the video indexing

Figure 2

 2 Figure 2 News trends over different periods

Figure 3

 3 Figure 3 Different displays of the same query results

Figure 6 Figure 5

 65 Figure 6 Cross lingual Search

Acknowledgments

This research was partially funded by the French funding agency OSEO in the QUAERO project. Vocapia Research provided the ASR (vocapia.com)