Department of Computer Science, UNC Chapel Hill

OpenCCL: Cache-Coherent Layouts of Meshes and Graphs

Contents of the Distribution

The archive contains all the libraries and include files needed to build applications using OpenCCL. However, source codes of METIS library that OpenCCL uses is not included; only METIS libraries for linux/Windows are included. If the METIS library included in the distribution causes some problems, please download it from its original distribution homepage. The following is a description of what each folder contains:

  1. libsrc: Source code for the OpenCCL library
  2. include: Include files for applications using OpenCCL
  3. example: One example demonstrating usage of the OpenCCL library
  4. VC_files: Project files for Microsoft Visual Studio 6.0
  5. Lib: Contains the OpenCCL library for Win32 and linux

Building an application

Setting up the library for use in your application is simple.

  1. Build the OpenCCL library (Please refer to README.txt in the distribution.)
  2. Make sure you link to OpenCCL.lib (or libOpenCCL.a on linux)
  3. The include folder included with the distribution should be in your include path
  4. Once the above two things have been done, all you need to do is "#include <OpenCCL.h>" and "using namespace OpenCCL;" in your application


Since the API of OpenCCL is very simple, instead of a function-by-function description of the class, we will present a simple example code to illustrate the usage. If you are looking for more elaborate information please go through OpenCCL.h, which contains elaborate function descriptions. .


An example

Below is a sample code snippet which orders input vertices given access patterns between them. To represent access patterns between vertices, edges between vertices are made.  

// Include OpenCCL header file and enable its namespace.
#include <OpenCCL.h>
using namespace OpenCCL;

int main()

	printf (" A sample mesh:\n"); 
	printf (" 0 -- 1\n"); 	
	printf (" | \\ |\n");	
	printf (" 2 __ 3\n");	

	// Specify the number of vertex that you are going to order.
	const int NumVertex = 4;	
	CLayoutGraph Graph (NumVertex);

	// make edges between vertices.
	Graph.AddEdge (0, 1);
	Graph.AddEdge (0, 2);
	Graph.AddEdge (0, 3);
	Graph.AddEdge (1, 3);
	Graph.AddEdge (2, 3);

	// Allocate an array  to hold computed ordering of vertices.	
	int Order [NumVertex];
	// Get ordering of the vertices given access patterns represented by edges.
	Graph.ComputeOrdering (Order); 

	printf ("Computed vertex order:\n");
	int i;
	for (i = 0;i < NumVertex;i++)
		printf ("ID of %dth position in the computed order is %d\n", i, Order [i]);	

... }

Note: Previously I wrote that ith vertex is mapped into Order [i]. But this is incorrect. Order [i] has an original vertex id in ith position in the computed vertex ordering. Sorry about the incorrect information.

The above code first creates CLayoutGraph object, which is an object that OpenCCL provides. The object requires an argument, which is the number of vertices that you are going to order. Next, you assign edges between vertices. It is very important to make edges between vertices that are going to be accessed sequentially at runtime. In this example, we simply make edges following the given mesh connectivity.

After finishing making edges, layout computation of vertices is invoked with an argument, an array to hold the resulting ordered sequence. The remaining code simply shows mapping between previous vertex index and new index in a computed order.

Once a CLayoutGraph object has been used, please create another one for another ordering computation.


The above code shows an example to order vertices of a mesh. However, you can use same example to order faces of a mesh or elements of a graph. For example, you can think of each face of a mesh as a node and make edges between nodes. Again, you need to carefully make edges between nodes of faces to represent cache-coherent access patterns on faces at runtime. Also, you can indirectly compute faces ordering given the computed vertex ordering. For example, as you access each vertex of the vertex ordering, you can sequentially place faces that are incident on the vertex in the face ordering without any duplication.



©2003 Department of Computer Science, UNC Chapel Hill