ACMR and ATVR

ACMR is Average Cache Miss Ratio, which is used to measure the effectiveness of a vertex reordering scheme to see how it performs. That is, the GPU has a certain number of transformed vertices it keeps in its post-transformed vertex cache. This cache will be more or less effective, depending on the order you feed triangles into the GPU. ACMR is the sum of the number of times each vertex must be transformed and loaded into the cache, divided by the number of triangles in the mesh. Under perfect conditions it is 0.5, since the most a cached vertex can be shared on average in a (non-bizarre) mesh is 6 times and each triangle has 3 vertices.

Ignacio Castaño has an excellent point: a better measure is to ignore the number of triangles in the mesh but instead divide by the number of vertices. He calls this the ATVR (average transform to vertex ratio) of a scheme. The problem with using the number of triangles is that this number varies with the mesh’s topology. Optimal ACMR, vertices over triangles, gives a sense of the amount of shared data in a mesh. ATVR is a better measure of cache performance, as it provides a number that can be judged by itself: 1.0 is always the optimum, so if your caching scheme is giving 1.05 ATVR, you’re doing pretty good. The worst ATVR can get is 6.0 (or just shy of 6.0).

I think the reason ACMR is used is that we evolved from triangle strips to connected meshes. Individual triangles have an ACMR of 3.0. Triangle strips have an optimum ACMR of 1.0, since each vertex can be shared with a maximum of 3 triangles. The way to think about triangle strips is how they increase sharing of vertices with triangles. Gluing strips together in a certain order allowed a better ACMR, since the vertices in one tristrip could be then reused by the next tristrip(s). So the ACMR as an optimum measure was a way to show why general meshes were worthwhile. But, once general meshes came to the fore and became the norm, this vertex/triangle ratio became less meaningful. At this point ACMR just makes it difficult to compare algorithms, as you alway need to know the optimum ACMR. The optimum ACMR changes from mesh to mesh. The optimum ATVR is always 1.0, so different meshes can be compared on the same scale.

That said, this comparison of different meshes using just ATVR can be a bit bogus: if a “mesh” was actually a set of disconnected triangles, no sharing, the ATVR would be 1.0 no matter what, since each vertex would always be transformed once and only once. ACMR would always be 3.0. So, the optimum ACMR is also good to know: a lower optimum ACMR means more sharing is possible and can be exploited.

Ignacio has a followup article on optimal grid rendering, showing the ACMR and ATVR for various schemes.

2 thoughts on “ACMR and ATVR

  1. Arseny Kapoulkine

    Optimum ACMR for a regular grid is ~0.5, so 1.0 is kind of wrong. ACMR of 1.0 is the ACMR for any non-indexed strip sequence (without degenerates, if you exclude them from counting, and for any sequence if you include everything).

    Btw, registration on a blog w/out OpenID is kind of lame.

  2. Eric Post author

    Yes, the optimum ACMR is 0.5 for a regular grid (or any closed mesh, for that matter – it’s all from Euler’s geometric formula; see pages 554-555 of the 3rd edition). I was indeed referring to the fact that for a single tristrip the ACMR approaches 1.0 at best (the more triangles, the closer to 1.0), since each vertex is shared by at most 3 triangles. Reading over my post, I made a typo, saying “meshes” where I meant to say “tristrips”. Fixed, and sorry about that. At least we got it right in the book.

    BTW, the “non-bizarre mesh” reference is like what you point out, that you could have some silly mesh like a single triangle repeated a million times. With this pathological case the ACMR drops nearly to 0.0: 3 vertices/million triangles.

    Naty’s the blogmaster, I’ve passed on your OpenID comment to him.

Comments are closed.