Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-05-28
2002-11-12
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S231000
Reexamination Certificate
active
06480876
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to executing applications having dynamically varying resource needs, and more particularly to executing the applications using integrated task and data parallelism.
BACKGROUND OF THE INVENTION
Task parallelism and data parallelism are distinct programming models for describing parallel application software programs.
In the prior art, a task parallel application is typically composed of a set of cooperating processes (“tasks”) that are implemented in a framework such as POSIX threads. In a task parallel application, the programmer explicitly defines the communication and synchronization functions between threads in the application. The application relies on the run-time system to schedule the execution of the threads on available processor resources, and to perform load-balancing over the resources.
In contrast, a prior art data parallel application is a single process that operates on distributed data. In a data parallel application, a compiler is usually responsible for generating efficient distributed code where communication overhead is minimized.
There is an emerging class of real-time interactive applications that require a dynamic integration of both task and data parallelism for effective implementation. One such application is described in U.S. patent application Ser. No. 08/844,444 “Method and Apparatus for Visual Sensing of Humans for Active Public Interface” filed on Apr. 8, 1997 by Waters et al., incorporated herein by reference.
There, an interactive, computerized kiosk is described that provides public access to information and entertainment. The kiosk supports natural, human-centered interaction with customers. A camera is used to sense the presence of one or more customers in front of the kiosk. The kiosk provides visual and audio feedback as long as customers are “sensed” in the kiosk's visible environment.
The location and number of customers control the “behavior” of a graphical talking “head” displayed on a monitor. The orientation of the talking depends on the location of the customer in the kiosk area. If there is more than one customer, then the talking head will divide its attention between the customers, much like a group interaction. For example, while talking to one customer, the eyes of the talking head may momentarily shift to others to make them feel part of the kiosk interaction.
The software application program that operates the kiosk has features that are typical of an emerging class of future scalable applications. The application is both reactive and interactive. For example, the kiosk (application) responds to changes in its environment. As new customers arrive, the kiosk will change its mode of interacting.
The application is computationally demanding due to the need for real-time vision, speech, and graphics processing. The application is also highly scalable. At the task level, i.e., processing threads, the application supports variable number of customers and functions. At the data level, multiple video and audio data streams may need to be processed.
At the hardware level, the kiosk application executes on a cluster of symmetric multi-processors (SMPs). SMPs provide a compelling platform for advanced applications such the kiosk system. Systems that use an SMP like architecture are economically attractive. Unfortunately, the flexibility provided by SMP clustering comes at the cost of a hierarchical communication model with multiple levels of locality. Conventional parallel programming models fail to handle one or more of these levels gracefully, making it difficult to program processor clusters effectively.
Applications such as the interactive kiosk exhibit both task and data parallelism. This is illustrated in
FIG. 1
which shows a task graph
100
for a basic vision application
100
within the total set of kiosk applications. The vision application tracks multiple customers in the kiosk environment according to, for example, the color of their clothing. In
FIG. 1
, two basic constructs are used, the nodes represent tasks, or execution threads, and the edges or “pipes” connecting the tasks are data flows.
A camera
101
is connected to a digitizer task (D). The camera
101
continuously monitors a scene in front of the kiosk. The digitizer task
110
produces a sequence of frames
111
at a predetermined rate. Each frame is composed of a plurality of picture element (pixel) values. A histogram task (H)
120
analyzes the frames to determine a predominant color of the clothing worn by customers standing in front of the kiosk. The histogram task
120
or “color tracker” produces color models
121
. Concurrently, motion masks
131
are produced by a change detector task (CD)
130
that also analyzes the frames
111
. The color models
121
and motion masks
131
are used by a target detector task (TD)
140
to track individuals in the scene.
Task parallelism is most obvious in the histogram task
120
and the change detection tasks
130
which have no data dependencies. That is, these two tasks can operate on their own copies of the same frames
111
at the same time. Task parallelism is also present in the form of pipelining, for example, the digitizing task
110
and the target detection task
140
can be performed simultaneously on different frames in the sequence.
Data parallelism is present in the target detection task
140
where multiple color targets (customers) can be detected in parallel. Potentially it should also be possible to exploit data parallelism in the change detection and the histogram tasks. For example, a single frame could be partitioned into a plurality of regions, and the regions, such as quadrants, could be processed in parallel.
Applications, such as the kiosk application, are not well-supported by either the task or the data parallel model alone because the kiosk application is made up of multiple distinct tasks which each provide opportunities for data parallel processing. As a result, maximum performance is not achieved under the task parallel model, and the application as a whole does not neatly fall into a traditional data parallel model.
Effective implementation of such real-time, interactive applications requires a hybrid parallel model that integrates both task and data parallelism within a single framework. Hybrid models that integrate task and data parallelism have been proposed in the prior art. Unfortunately, previous approaches require either a static problem domain, or a highly restricted application domain such as is found in numerical linear algebra.
One prior art system describes a framework for exploiting task parallelism in dynamic multi-media applications such as the color tracker. This work is described in U.S. patent application Ser. No. 08/909,405, “Space-Time Memory” filed by Ramachandran et al. on Aug. 11, 1997. That system was designed to match the dynamic data flow and heterogeneous task requirements of multi-media applications involving, for example, concurrent video and speech processing.
In that framework, tasks are implemented as threads, and the run-time system relies on the operating system to effectively schedule processor resources. That prior art task parallel system lacks any type of mechanism for incorporating data parallelism into its framework.
A number of prior art task parallel systems do include integrated task and data parallelism, the “Orca” and the “FX” system are two examples. However, Orca falls short in that its data parallelism is not only static, but also specified explicitly in the source programs of the application. The FX system is significantly more advanced. It automatically determines optimal mappings of tasks to processors in static domains where the flow of the computation does not vary as a function of the data, but remains fairly consistent over a variety of data sets.
Unfortunately, the parallelism exhibited by multi-media applications, like the color tracker above, is often highly dynamic, because the required processing is determined by the video content, for example, the number of customers in t
Knobe Kathleen
Nikhil Rishiyur S.
Ramachandran Umakishore
Rehg James Mathew
Courtenay III St. John
Hamilton, Brook, Smith and Reynolds, P.C.
Nguyen Van H.
LandOfFree
System for integrating task and data parallelism in dynamic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for integrating task and data parallelism in dynamic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for integrating task and data parallelism in dynamic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2945653