Archive for the ‘Graph Coloring’ Category

Graph Motif Resume

Friday, September 7th, 2012

An (almost complete) state of the art around the Graph Motif problem by Florian Sikora.

A listing of current (March, 2012) results on the Graph Motif problem, including references to software.

Starts with an intuitive illustration of the problem.

Makes it easy to see why this problem is going to command a lot of attention as more complex (and realistic) modeling becomes commonplace.

Or to put it another way, normalized data is just that, normalized data. That’s why we don’t call it reality.

Zoltan: Parallel Partitioning, Load Balancing and Data-Management Services

Friday, March 30th, 2012

Zoltan: Parallel Partitioning, Load Balancing and Data-Management Services

From project motivation:

Over the past decade, parallel computers have been used with great success in many scientific simulations. While differing in their numerical methods and details of implementation, most applications successfully parallelized to date are “static” applications. Their data structures and memory usage do not change during the course of the computation. Their inter-processor communication patterns are predictable and non-varying. And their processor workloads are predictable and roughly constant throughout the simulation. Traditional finite difference and finite element methods are examples of widely used static applications.

However, increasing use of “dynamic” simulation techniques is creating new challenges for developers of parallel software. For example, adaptive finite element methods refine localized regions the mesh and/or adjust the order of the approximation on individual elements to obtain a desired accuracy in the numerical solution. As a result, memory must be allocated dynamically to allow creation of new elements or degrees of freedom. Communication patterns can vary as refinement creates new element neighbors. And localized refinement can cause severe processor load imbalance as elemental and processor work loads change throughout a simulation.

Particle simulations and crash simulations are other examples of dynamic applications. In particle simulations, scalable parallel performance depends upon a good assignment of particles to processors; grouping physically close particles within a single processor reduces inter-processor communication. Similarly, in crash simulations, assignment of physically close surfaces to a single processor enables efficient parallel contact search. In both cases, data structures and communication patterns change as particles and surfaces move. Re-partitioning of the particles or surfaces is needed to maintain geometric locality of objects within processors.

We developed the Zoltan library to simplilfy many of the difficulties arising in dynamic applications. Zoltan is a collection of data management services for unstructured, adaptive and dynamic applications. It includes a suite of parallel partitioning algorithms, data migration tools, parallel graph coloring tools, distributed data directories, unstructured communication services, and dynamic memory management tools. Zoltan’s data-structure neutral design allows it to be used by a variety of applications without imposing restrictions on application data structures. Its object-based interface provides a simple and inexpensive way for application developers to use the library and researchers to make new capabilities available under a common interface.

The NoSQL advocates only recently discovered “big data.” There are those who have thought long and deep about processing issues for “big data.” New approaches and techniques will go further if compared and contrasted to prior understandings. This is one place for such an effort.