PaToH v3.0
PaToH (Partitioning Tools for Hypergraph) is a
Multilevel Hypergraph Partitioning tool that I developed during my
doctoral studies at Bilkent University (1994-1999). Unfortunately, I have
never had enough time to write a complete manual to make the
software tool suitable for distribution. It was the fastest hypergraph
partitioner when I wrote it, and may be the fastest
partitioner to this day. You are welcome to review the incomplete manual in [ps] or [pdf] format.
Important features of PaToH:
- Fast, stable multilevel hypergraph partitioner,
- Hypergraph partitioning with fixed cells,
- Multi-constraint hypergraph partitioner.
PaToH distributions for different architectures:
If you are interested in running PaToH on a different platform,
please notify me, and I will attempt to prepare a version
for your preferred platform provided I have access to it.
If you have questions or
comments about the PaToH, please email me or Prof. Dr. Cevdet
Aykanat who was my advisor at Bilkent University.
Latest Changes:
- 5/12/06: Fixed the memory alignment on 64-bit libraries,
improving the performance significantly on IA64 architectures. Thanks
to Duraid Madina for noticing the alignment problem on IA64 and
suggesting the fix!
- 1/10/05: Changed the default behavior to continue to
partition, with default values, if the chosen algorithm is not
implemented in the particular partitioner Also a minor balance
improvement was made.
- 11/11/04: Mac OS X distribution has been added.
- 8/15/02: Fixed a couple of small bugs and changed the
default values of a few parameters.
Data & Results
- Exp-1: ISPD98: 2% actual area results comparison with hMeTiS and UCLA MLPart
- Exp-2:
Comparison of hMeTiS and PaToH on 134 hypergraphs arising from different
areas, Sparse-Matrix Vector Multiplication, LP, VLSI
(including ISPD98).
Related Publications:
- Hypergraph-Partitioning Based Decomposition for Parallel
Sparse-Matrix Vector Multiplication. U. Catalyurek and C. Aykanat. IEEE Transaction on
Parallel and Distributed Systems, Vol. 10, No. 7, pp. 673-693, 1999. [ps] [pdf]
- A
Hypergraph-Partitioning Approach for Coarse-Grain
Decomposition. U. Catalyurek and C. Aykanat. ACM/IEEE SC2001, Denver, CO, November 2001. [ps] [pdf]
- A Fine-Grain
Hypergraph Model for 2D Decomposition of Sparse Matrices. U. Catalyurek and C. Aykanat. Proceedings of International Parallel and Distributed Processing
Symposium (IPDPS), 8th International Workshop on Solving Irregularly
structured Problems in Parallel (Irregular 2001), San Francisco, April
2001. [ps] [pdf]
- Decomposing
irregularly sparse matrices for parallel matrix-vector
multiplications. U. Catalyurek and C. Aykanat. Lecture Notes in Computer Science, vol.
1117, pp. 75-86, 1996. [ps] [pdf]
- Decomposing linear programs for parallel
solution. A. Pinar, U. Catalyurek, C. Aykanat, and M. Pinar. Lecture Notes in Computer Science, vol. 1041, pp.
473-482, 1996. [ps] [pdf]
- A hypergraph model for mapping repeated sparse
matrix-vector product computations onto multicomputers. Ü. V. Çatalyürek and C.
Aykanat, Proceedings of International Conference on High Performance Computing,
HiPC ’95, Goa, India, December 1995. [ps] [pdf]
top, complete list of publications
Zoltan:
Zoltan, developed and maintained by Sandia National Laboratories,
is a toolkit for load balancing and parallel data management. In the last couple of years,
I had the pleasure of collaborating with the Zoltan team. As an outcome of this collaboration
we developed a parallel multilevel hypergraph partitioning algorithm,
as well as distance-1 and distance-2 coloring algorithms. Zoltan release v2.0 (and later)
includes the implementation of these algorithms and its source code is distributed under the GNU Lesser General Public License.
More information and the distribution of Zoltan can be found at the project web site.
top
DataCutter:
DataCutter is a component-based middleware framework designed
to support coarse-grain data-flow execution on heterogeneous environments. In DataCutter,
application processing structure is implemented as a set of components, named filters,
that exchange data through logical streams. A stream denotes
an uni-directional data flow from one filter (i.e., the producer) to another (i.e., the consumer).
A filter is required to read data from its input streams and write data to its output streams only.
The DataCutter runtime system supports both data- and task-parallism. Processing, network and data
copying overheads are minimized by the ability to place filters on different platforms.
DataCutter's filtering service performs all steps necessary to instantiate filters
on the desired hosts, to connect all logical endpoints, and to call the filter's interface
functions for processing work. Data exchange between two filters on the same host
takes place by memory copy operations, while a message passing communication layer (e.g. TCP sockets or MPI)
is used for communication between filters on different hosts.
More information and the distribution of DataCutter can be found at the project web site.
top
STORM:
STORM is a middleware, being built using DataCutter, that is designed to provide basic database support for
1) Selection of the data of interest, 2) Transfer of data from storage nodes to compute nodes for processing.
STORM is designed as a set of coupled services. The query service provides an entry point for clients
to submit queries to the database middleware. It is responsible for parsing the client query to determine which
services should be instantiated to answer the query. The metadata service maintains information about datasets,
and indexes and user-defined filters associated with the datasets. The data source service provides a view
of a dataset as virtual tables to other services. Efficient execution of select operations is supported by
indexing service and filtering service. The filtering service supports efficient execution
of user-defined filters. The purpose of the partition generation service is to make it possible for an
application developer to export the data distribution scheme employed in a parallel client program.
The data mover transfers the selected data elements to the client based on the partitioning
information returned from the partition generation service.
STORM has been integrated and distributed with the NSF Middleware Initiative, since Release 5
More information and the distribution of STORM can be found at the project web site.
top
MSSG:
Developing scalable algorithms for relationship analysis on social network graphs (also known as semantic graphs) has been identified as an important need by the Department of Homeland Security. Unlike graphs from most scientific applications, in a scale-free graph most of the vertices are connected only to a small number of other vertices, while a few vertices, known as hubs, are connected to a large number of other vertices. This extreme irregularity requires novel data structures and databases to store these large graphs. We have recently started developing a framework that will support storage, retrieval and processing of large scale-free semantic graphs.
top
