News Column

Researchers Submit Patent Application, "Visualization Tool for Parallel Dependency Graph Evaluation", for Approval

February 27, 2014



By a News Reporter-Staff News Editor at Politics & Government Week -- From Washington, D.C., VerticalNews journalists report that a patent application by the inventors WATT, Martin Peter (Glendale, CA); Duncan, Brendan (Redwood City, CA), filed on March 12, 2013, was made available online on February 13, 2014.

The patent's assignee is DreamWorks Animation LLC.

News editors obtained the following quote from the background information supplied by the inventors: "This application relates generally to visualization tools for computer processes and, more specifically, to computer systems and processes for visualizing the state of parallel dependency graph evaluation in computer animation.

"Visualization tools are available for displaying a graphical representation of the performance of a computer program. For example, traditional visualization tools may provide a heat map that aids programmers, among others, to identify the most expensive, lengthy processes or functions that account for longer program runtimes and decreased user satisfaction. A programmer may then focus on optimizing the most expensive, lengthy processes or functions so as to have the greatest impact on decreasing runtime and improving user satisfaction.

"However, while traditional visualization tools may be helpful for serial processes, they are less helpful and may even be misleading for multithreaded programs with processes running in parallel. To take advantage of multi-core processors capable of processing two, four, eight, twelve, sixteen, or more threads in parallel, programmers, among others, are designing programs with multiple threads that can run simultaneously, thereby decreasing runtime and improving overall performance. Traditional visualization tools may identify lengthy processes running on each of the multiple cores, but optimizing those processes may, in fact, have little or no impact on a program's overall runtime, thereby misleading programmers and wasting time.

"For example, a lengthy process may run concurrently with a chain of serially dependent processes that run for a longer period of time than the concurrently running lengthy process. Traditional visualization tools may suggest that optimizing the lengthy process will decrease overall runtime when, in fact, it will have no effect on the overall runtime since the serially dependent processes running concurrently, despite each being shorter in duration, together are of a longer duration. In such a case, optimization efforts should be directed at the serially dependent processes, but current visualization tools may not lead to that conclusion.

"Optimization concerns are especially pertinent in the area of computer animation, where hundreds of thousands of animation frames may be processed to create the complex and detailed scenes in today's animated films. Character technical directors, character riggers, and the like may develop a dependency graph to render, animate, or otherwise describe a scene in an animation. A dependency graph may be made up of interconnected nodes, each of which may be a standalone computation unit that takes in data via one or more input attributes, performs some computation on the data, and produces one or more output attributes. The connections in the graph may represent data flowing from one node to the next, with each node performing some computation on the data it receives to generate its output. A node may have multiple inputs and multiple outputs, as well as other attributes.

"Many nodes may be computed simultaneously on multiple processor cores, but computing chains of nodes, each depending on the last, may require significant processing time. Optimization efforts should, therefore, be directed at those chains of nodes that directly impact the time it takes to evaluate a dependency graph. However, traditional visualization tools may lead character technical directors, character riggers, and the like to focus on optimizing non-critical nodes rather than the key nodes that directly impact the time it takes for the dependency graph to evaluate.

"Thus, an improved visualization tool for parallel dependency graphs (as well as other multithreaded computer processes) is desired."

As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventors' summary information for this patent application: "Systems and processes for generating a performance visualization of a parallel dependency graph are described. A data file may be received that includes runtime evaluation entries for nodes in a parallel dependency graph. Runtime evaluation entries may include node identification and runtime duration. The concurrency level for each node in the parallel dependency graph may be determined based on the number of concurrently executing nodes in the data file. A node block may be generated for each of the nodes in the parallel dependency graph. The size and the position of each of the node blocks may be determined based on the concurrency level and runtime duration of each corresponding node. A performance visualization may be generated with some or all of the node blocks with sizes and at positions as determined from the concurrency level and runtime duration of the corresponding nodes.

"A request may be received for characteristics of a particular node block in the performance visualization. In response to receiving the request for characteristics, the corresponding node identification, start time, and stop time may be provided for the particular node block. The upstream derivation and downstream progeny may also be identified and provided for the particular node block. A display property of node blocks may also be changed based on the upstream derivation and downstream progeny. A critical path of nodes through the parallel dependency graph may also be determined based on a chain of nodes in the parallel dependency graph with the longest runtime duration. The position of node blocks in the performance visualization may be determined based on the critical path of nodes through the parallel dependency graph. A display property of node blocks may also be changed based on the critical path of nodes.

BRIEF DESCRIPTION OF THE FIGURES

"The present application can be best understood by reference to the following description taken in conjunction with the accompanying drawing figures, in which like parts may be referred to by like numerals.

"FIG. 1 illustrates an exemplary computer-generated animation scene.

"FIG. 2 illustrates an exemplary visualization tool that may be used to optimize parallel dependency graph evaluation in computer animation.

"FIG. 3 illustrates an exemplary parallel dependency graph with interconnected nodes.

"FIG. 4 illustrates an exemplary computer-generated animation scene.

"FIG. 5 illustrates an exemplary performance visualization of a parallel dependency graph evaluation.

"FIG. 6 illustrates an exemplary performance visualization generated from evaluating a parallel dependency graph animating a scene of a film.

"FIG. 7A illustrates an exemplary process for generating a performance visualization of a parallel dependency graph evaluation.

"FIG. 7B illustrates an exemplary process for generating a performance visualization that emphasizes the critical path of nodes in a parallel dependency graph.

"FIG. 8 illustrates an exemplary computing system."

For additional information on this patent application, see: WATT, Martin Peter; Duncan, Brendan. Visualization Tool for Parallel Dependency Graph Evaluation. Filed March 12, 2013 and posted February 13, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=5169&p=104&f=G&l=50&d=PG01&S1=20140206.PD.&OS=PD/20140206&RS=PD/20140206

Keywords for this news article include: DreamWorks Animation LLC.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering arts and entertainment, please see HispanicBusiness' Arts & Entertainment Channel



Source: Politics & Government Week


Story Tools