News Column

Patent Issued for Distribution Data Structures for Locality-Guided Work Stealing

September 2, 2014

By a News Reporter-Staff News Editor at Information Technology Newsweekly -- From Alexandria, Virginia, VerticalNews journalists report that a patent by the inventors Maessen, Jan-Willem (Somerville, MA); Dias, Jaao P. (Watertown, MA), filed on August 4, 2008, was published online on August 19, 2014.

The patent's assignee for patent number 8813091 is Oracle America, Inc. (Redwood City, CA).

News editors obtained the following quote from the background information supplied by the inventors: "This invention relates generally to distributed computing, and more particularly to systems and methods for tracking the locations of distributed computations and/or data for a subdivided iteration space.

"Parallel programming has traditionally involved a tradeoff between two competing factors: the desire to express the solution to a scientific problem as simply and naturally as possible, and the need to effectively utilize the large computational resources required to obtain a solution. For the foreseeable future, the cost of communication in a large parallel machine will continue to be a limiting factor for performance. This dichotomy, then, may be viewed as a tradeoff in program structure. In other words, in some cases, a program may be structured around its communication. For example, it may be structured via explicit message passing using the Message Passing Interface (MPI) standard. In other cases, a problem may be expressed as naturally as possible with the hope of obtaining a reasonably efficient code that is adaptable and easily maintained.

"Physical simulations, the stock-in-trade of parallel computing, often focus on propagating phenomena (matter, force, energy) through space. Arrays of floating-point numbers are common currency for such spatial simulation. These arrays must be carved up, either explicitly or implicitly, into pieces that can be distributed across a machine. Similarly, computations on these arrays must be carved up into pieces suitable for executing in parallel.

"Individual processors are becoming parallel machines in miniature. This combined with the increasing size of large parallel machines means that parallel computing systems will have to expose, and load balance, several orders of magnitude more computation than currently available parallel machines. However, even current approaches often fail, as evidenced by the low utilizations of most large parallel machines."

As a supplement to the background information on this patent, VerticalNews correspondents also obtained the inventors' summary information for this patent: "Systems and methods for providing a data structure, the distribution, which may be used to track the desired and/or actual locations of computations and data that range over a multidimensional iteration space (e.g., a rectangular index space) are disclosed. Examples of such iteration spaces include multidimensional arrays (e.g., multidimensional arrays supported by the Fortran or Fortress programming languages and having arbitrary indices) and counted loop nests. In various embodiments, these distribution data structures may be used in conjunction with locality-guided work stealing in systems that support work stealing.

"In some embodiments, the use of distribution data structures may allow computations to be tied to array layout, and may allow iterations over subspaces of an index space to be performed in a manner consistent with the layout of the index space itself. For example, iterating over one half of an existing distributed array may by default occur on the processor(s) where that half of the array is allocated. In some embodiments, a common two-level layout may be used for all distributed arrays. Multiple arrays may be allocated such that they are aligned. In other words, smaller arrays may be aligned in memory alongside portions of larger arrays.

"A distribution data structure may in some embodiments provide a structured mechanism to track load balancing decisions so that they can be reproduced in related computations, thus maintaining locality of reference. Such a data structure may provide a means for tracking locality information while providing load balancing based on work stealing, in some embodiments. Distribution data structures may also offer an opportunity to describe computations in a manner that is oblivious to precise machine size or structure."

For additional information on this patent, see: Maessen, Jan-Willem; Dias, Jaao P.. Distribution Data Structures for Locality-Guided Work Stealing. U.S. Patent Number 8813091, filed August 4, 2008, and published online on August 19, 2014. Patent URL:

Keywords for this news article include: Oracle America Inc, Information Technology, Information and Data Architecture.

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

For more stories covering the world of technology, please see HispanicBusiness' Tech Channel

Source: Information Technology Newsweekly

Story Tools Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters