Global Trees

From HPCRL Wiki
(Difference between revisions)
Jump to: navigation, search
Line 14: Line 14:
  
  
−
== Scioto Programming Model ==
+
== Global Trees Programming Model ==
  
−
Scioto provides the user with a task pool programming model. Under this model the user expresses their computation as a set of ''tasks'' that can be executed in parallel.  Tasks read inputs from their task descriptor as well as from data stored in the global address space. Tasks store their output in the global address space and are also permitted to add new tasks to the task collection.
+
Global Trees provides a get/compute/put model for working with globally shared data. The user defines a data structure which contains a GT header structure for link/connectivity information (such as the child pointers) and then calls GT routines for manipulating these structures. Global pointers are dereferenced by get operations and updates are made with put operations.
 +
Scioto provides the user with a task pool programming model.
  
−
Below is pseudocode that shows the structure of a simple Scioto program.
+
Below is pseudocode that shows the structure of a simple recursive GT tree copy operation.
  
 
<pre>
 
<pre>
−
// The user decides how to store task arguments within the task
+
void main(int *argc, char **argv) {
−
// body.  Generally, users define a struct to organize this data.
+
  gt_context_t *gtc = gt_init(&argc, &argv);
−
typedef struct {
+
  gt_tree_t stree = my_create_a_tree(gtc, ...); // application-defined
−
  double args;
+
−
} mytask_t;
+
  
−
// The user provides a function that implements the task.  This
+
  gt_tree_t dtree = gt_tree_create(gtc, ...);
−
// function is run by Scioto when executing the task.
+
−
void task_fcn(gtc_t gtc, task_t *my_task) {
+
−
  // ...
+
−
}
+
  
−
int main() {
+
   tree_copy(dtree, gt_get_root(stree), gt_get_root(dtree));
−
  gtc_t    tc   = gtc_create(...);      // Create a task collection
+
}
−
  task_t  task = gtc_task_create(...); // Create a task descriptor
+
−
  mytask_t my_t = gtc_task_body(task); // Get the task body
+
−
 
+
−
  my_t.args = ...;    // Fill in the task's arguments
+
  
−
  gtc_task_add(task); // Add the task to the task collection
 
  
−
  gtc_process(tc);   // Enter task-parallel region
+
void tree_copy(gt_tree_t ng, gt_cnp_t *src, gt_cnp_t *dst) {
 +
  gt_cnp_t *schild, *dchild;
 +
  gt_node_t snode, dnode;
 +
  int i;
 +
 
 +
  snode = gt_get_node(ng, src);
 +
  dnode = gt_get_node(ng, dst);
 +
 
 +
  for (i=0;i<NUM_CHILDREN;i++) {
 +
    schild = gt_get_child(ng, snode, i);
 +
    if (gt_is_active(schild)) {
 +
      dchild = gt_node_alloc(ng, dst);
 +
      gt_link_child(ng, dst, dnode, i, dchild);
 +
      tree_copy(ng, schild, dchild);
 +
    }
 +
  }
 +
  gt_put_node(ng, dst, dnode);
 +
  gt_finish_node(ng, snode);
 
}
 
}
 
</pre>
 
</pre>
Line 50: Line 57:
 
=== Programming Interface ===
 
=== Programming Interface ===
  
−
Documentation on Scioto's user API can be found here: [[Scioto API]]
+
Documentation on Global Trees user API can be found here: [[GT API]]
  
 
=== Publications ===
 
=== Publications ===
  
−
'''Scalable Work Stealing'''
+
'''Global Trees: A Framework for Linked Data Structures on Distributed
−
[http://www.cse.ohio-state.edu/~dinan/research/tpool/dinan_sc09.pdf PDF]
+
Memory Parallel Systems"' [http://www.cse.ohio-state.edu/~larkins/larkins_sc08.pdf PDF]  
−
[http://www.cse.ohio-state.edu/~dinan/research/tpool/dinan_sc09_slides.ppt PPT]
+
D. Brian Larkins, James Dinan, Sriram Krishnamoorthy, Atanas Rountev , P. Sadayappan Proc. 20th
−
<br />
+
Intl. Conference on Supercomputing (SC). Austin, TX, Nov. 15-21, 2008.
−
James Dinan, Sriram Krishnamoorthy, D. Brian Larkins, Jarek Nieplocha, P. Sadayappan <br />
+
−
Proc. 21st Intl. Conference on Supercomputing (SC). Portland, OR, Nov. 14-20, 2009.
+
−
 
+
−
'''Scioto: A Framework for Global-View Task Parallelism'''
+
−
[http://www.cse.ohio-state.edu/~dinan/research/tpool/dinan_icpp08.pdf PDF]
+
−
[http://www.cse.ohio-state.edu/~dinan/research/tpool/dinan_icpp08_slides.ppt PPT]
+
−
<br />
+
−
James Dinan, Sriram Krishnamoorthy, D. Brian Larkins, Jarek Nieplocha, P. Sadayappan <br />
+
−
Proc. of 37th Intl. Conference on Parallel Processing. Portland, OR, Sept. 8-12, 2008.
+
  
 
== Project Members ==
 
== Project Members ==

Revision as of 18:30, 14 July 2010

Global Trees and Global Chunks are frameworks for supporting global view programming of irregular data structures on distributed memory machines. This framework allows the user to create, update, and access distributed tree structures in a global fashion, using one-sided operations for access. This system allows for parallel computations on these data structures in an asynchronous manner. Communication operations are automatically mapped to bulk data movement, allowing for efficient fine-grained access of tree data.

Both Global Trees (GT) and Global Chunks (GCL) use ARMCI and MPI internally. We have tested interoperability with MPI, ARMCI, and Global Arrays applications and are investigating interoperability with additional parallel programming tools.


Contents

Global Trees Programming Model

Global Trees provides a get/compute/put model for working with globally shared data. The user defines a data structure which contains a GT header structure for link/connectivity information (such as the child pointers) and then calls GT routines for manipulating these structures. Global pointers are dereferenced by get operations and updates are made with put operations. Scioto provides the user with a task pool programming model.

Below is pseudocode that shows the structure of a simple recursive GT tree copy operation. 

void main(int *argc, char **argv) {
  gt_context_t *gtc = gt_init(&argc, &argv);
  gt_tree_t stree = my_create_a_tree(gtc, ...); // application-defined

  gt_tree_t dtree = gt_tree_create(gtc, ...);

  tree_copy(dtree, gt_get_root(stree), gt_get_root(dtree));
}


void tree_copy(gt_tree_t ng, gt_cnp_t *src, gt_cnp_t *dst) {
  gt_cnp_t *schild, *dchild;
  gt_node_t snode, dnode;
  int i;
  
  snode = gt_get_node(ng, src);
  dnode = gt_get_node(ng, dst);
  
  for (i=0;i<NUM_CHILDREN;i++) {
    schild = gt_get_child(ng, snode, i);
    if (gt_is_active(schild)) {
      dchild = gt_node_alloc(ng, dst);
      gt_link_child(ng, dst, dnode, i, dchild);
      tree_copy(ng, schild, dchild);
    }
  }
  gt_put_node(ng, dst, dnode);
  gt_finish_node(ng, snode);
}

Documentation

Programming Interface

Documentation on Global Trees user API can be found here: GT API

Publications

Global Trees: A Framework for Linked Data Structures on Distributed Memory Parallel Systems"' PDF D. Brian Larkins, James Dinan, Sriram Krishnamoorthy, Atanas Rountev , P. Sadayappan Proc. 20th Intl. Conference on Supercomputing (SC). Austin, TX, Nov. 15-21, 2008.

Project Members

Acknowledgements

This research was supported in part by DOE grant #DE-FC02-06ER25755 and NSF grant #0403342.

Download

We are currently providing early development snapshots for download. Please see the included README file for installation instructions. For questions or comments, contact Brian Larkins (blarkins at coastal dot edu).

  • Dev Release, 0.2 - July 2010 - [1]
Retrieved from "http://hpcrl.cse.ohio-state.edu/wiki/index.php/Global_Trees"
Personal tools