Finite Presentations of Pregroups and the Identity Problem.
Alexa H. Mater and James D. Fix. Appeared in FGMoL '05.

Optimal Routing in Bidirectional Variants of Chord.
James D. Fix and Jeffrey Green. Unpublished manuscript, 2004

Offline 1-Minesweeper is NP-complete.
James D. Fix and Brandon McPhail. Unpublished manuscript, 2004

Set-Associative Cache Performance of Search Trees.
Appeared in SODA '03.

Cache Performance Analysis of Algorithms.
Ph. D. dissertation. University of Washington, 2002.

Cache Performance Analysis of Traversals and Random Accesses.
Richard E. Ladner, James D. Fix and Anthony LaMarca. Appeared in SODA '99.

Multiresolution Banded Refinement to Accelerate Surface Reconstruction from Polygons.
James D. Fix and Richard E. Ladner. Appeared in Computational Geometry '98. Also in Journal of Computational Geometry: Theory and Applications.

Combinatorial Optimization through Multiresolution Analysis. Submitted for my General Examination, 1996.

Sorting by Parallel Insertion on a One-Dimensional Sub-Bus Array.
James D. Fix and Richard E. Ladner. Appeared in IEEE Transactions on Computers.

Optimal Sorting on a One-dimensional Sub-bus Array.
James D. Fix and Richard E. Ladner. Appeared in SODA '95.

Finite Presentations of Pregroups and the Identity Problem

Abstract:
We consider finitely generated pregroups, and describe how an appropriately defined rewrite relation over words from a generating alphabet yields a natural partial order for a pregroup structure. We investigate the identity problem for pregroups; that is, the algorithmic determination of whether a word rewrites to the identity element. This problem is undecidable in general, however, we give a dynamic programming algorithm and an algorithm of Oehrle(2004) for free pregroups, and extend them to handle more general pregroup structures suggested in Lambek (1999). Finally, we show that the identity problem for a certain class of non-free pregroups is NP-complete.
Citation:
Alexa H. Mater and James D. Fix.
"Finite presentations of pregroups and the identity problem"
In Proceedings of the 10th conference on Formal Grammar and The 9th Meeting on Mathematics of Language (FGMoL05)
August 2005.
On-line documents:
final version

Optimal Routing in Bidirectional Variants of Chord

Abstract:
A Chord network [Stoica et al.], used for an implementation of a distributed dictionary, is structured as a ring of nodes with connections at offsets of powers of base two around the ring. We consider routing algorithms for a bidirectional variant of Chord networks and show that the structure of optimal routes in these networks is exactly characterized by their specification as signed bit representations of integers. We determine optimal routes using a simple rewrite system over these route specifications and thus exactly characterize minimal signed bit representations. We give an algorithm to determine an optimal route from the ring offset between the route's source and destination.

We extend our rewrite system approach to study optimal routing in networks for bases greater than two, generalizing our results to find minimal signed digit representations. Such represen- tations provide an elegant characterization of routing for these networks, and their study has applicability to computer systems and computer arithmetic in general.

Citation:
James D. Fix and Jeffrey Green.
"Optimal Routing in Bidirectional Variants of Chord"
Unpublished manuscript, August 2004.
On-line documents:
current version

Offline 1-Minesweeper is NP-complete

Abstract:
We use Minesweeper to illustrate NP-completeness proofs, arguments that establish the hardness of solving certain problems. In particular, we give a polynomial time reduction from boolean circuits to Minesweeper puzzles where each square in the puzzle has at most one mine surrounding it. Our construction encodes circuits as Minesweeper puzzles that look easy to solve, and suggests that solving Minesweeper puzzles off-line is hard even when the density of mines is low.

Citation:
James D. Fix and Brandon McPhail.
"Offline 1-Minesweeper is NP-complete"
Unpublished manuscript, July 2004.
On-line documents:
current version

Cache Performance Analysis of Algorithms

Abstract:

How effectively a program uses the memory hierarchy of a computer system can have a tremendous impact on its performance. The failure of a program to access data in the cache memory, hence the need to access that data in main memory, has a cost of up to 100 cycles on today's systems, a penalty that is expected to rise with future systems. As a result much recent algorithm design research has been conscious of the cache, and has focused on its effective use. Understanding the behavior of the cache when developing algorithms is crucial to such research.

We develop the cache performance analysis of algorithms whose primary goal is to determine the number of cache hits and cache misses that an algorithm incurs. We view an algorithm as a combination of basic memory access patterns, analyze each pattern's cache performance, and apply the analysis to accurately predict the cache performance of the algorithm. Our analysis is precise: we pay attention to constant factors and quantify performance for even moderate data sizes. Our caching model is realistic: we determine the performance of our access pattern models for direct-mapped caches and caches with a limited degree of set-associativity. For certain patterns that arise in accessing common data structures, we demonstrate and prove that set-associativity yields little or no benefit over direct-mapped caching.

Citation:

James D. Fix.
Cache Performance Analysis of Algorithms.
PhD dissertation, University of Washington, January 2002.

On-line documents:

thesis

The Set-Associative Cache Performance of Search Trees

Abstract:

We consider the costs of access to data stored in search trees assuming that those memory accesses are managed with a cache. Our cache memory model is two-level, has a small degree of set-associativity, and uses LRU replacement, and we consider the number of cache misses that a set of accesses incurs. For standard tree access--- searches and traversals--- changing the degree of set-associativity has no effect on performance.

To explain this, we develop general stochastic access models, an adaptation of the independent reference model (IRM), and analyze the expected number of cache hits and misses incurred by these types of access. The models and analyses are accurate: we are able to exactly predict the cache performance of tree data structures. In addition, we prove why set-associativity is of little or no benefit for these types of memory access and give examples where direct-mapping performs better than set-associativity.

Citation:

James D. Fix.
"Cache Performance Analysis of Traversals and Random Accesses".
In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms., January 2003.

On-line documents:

final version

Cache Performance Analysis of Traversals and Random Accesses

Abstract:

This paper describes a model for studying the cache performance of algorithms in a direct-mapped cache. Using this model, we analyze the cache performance of several commonly occurring memory access patterns: (i) sequential and random memory traversals, (ii) systems of random accesses, and (iii) combinations of each. For each of these, we give exact expressions for the number of cache misses per memory access in our model. We illustrate the application of these analyses by determining the cache performance of two algorithms: the traversal of a binary search tree and the counting of items in a large array. Trace driven cache simulations validate that our analyses accurately predict cache performance.

Citation:

Richard Ladner, James D. Fix, and Anthony LaMarca.
"Cache Performance Analysis of Traversals and Random Accesses".
In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms., January 1999.

On-line documents:

preprint

Multiresolution Banded Refinement to Accelerate Surface Reconstruction from Polygons.

Abstract:

We propose a method for constructing a tiling between a pair of planar polygons. Our technique uses multiresolution: tilings of lower resolution polygons are used to construct a tiling for the full resolution polygons. The tilings are constructed using restricted dynamic programming called banded refinement in roughly linear time and space. By contrast, the optimal dynamic programming method requires quadratic time and space. In our empirical study of surface reconstruction of brain contours our algorithm exhibited significant speedup over the optimal dynamic program, yet nearly always achieved the optimal reconstruction. Our approach appears to be generalizable to other geometric problems solvable by dynamic programming, and flexible enough to be tuned to varying data set characteristics.

Citation:

James D. Fix and Richard E. Ladner. "Multiresolution Banded Refinement to Accelerate Surface Reconstruction from Polygons." In Proceedings of the 14th Annual Symposium on Computational Geometry, June 1998, pages 240-248. An expanded version of this paper will appear in Elsevier Science Journal of Computational Geometry: Theory and Applications Special Issue on Applied Computational Geometry.

On-line documents:

final submission (uncompresses to 1.5M)

journal preprint (uncompresses to 2.5M)

Combinatorial Optimization through Multiresolution Analysis.

Abstract:

Recently, multiresolution analysis and wavelets have had a great impact on computer algorithm design, chiefly in the areas of signal processing and compression, computer graphics, and numeric optimization algorithms. Of the algorithms that have benefitted, Meyers multiresolution polygon tiling algorithm is unique in that it solves a combinatorial optimization problem. This paper suggests a generalization of Meyers' methodology by proposing an algorithm framework called multiresolution optimization. The idea behind multiresolution optimization is simple: simplify a problem instance by constructing a lower resolution version, solve the optimization problem on this simpler version, and use the solution of the simpler instance to construct a solution to the original problem instance. We discuss the potential benefits of multiresolution algorithms, and the issues involved in their design.

Citation:

James D. Fix. "Combinatorial optimization through multiresolution analysis." Unpublished manuscript submitted for the University of Washington General Examination, January 1996.

On-line documents:

unpublished manuscript

Sorting by Parallel Insertion on a One-Dimensional Sub-Bus Array.

Abstract:

We consider the problem of sorting on a one-dimensional sub-bus array of processors, an architecture that communicates using a segmentable bus. The sub-bus broadcast operation makes possible a new class of parallel sorting algorithms whose complexity we analyze with the parallel insertion model. We give per-input lower bounds for sorting in the parallel insertion model, and demonstrate sorting strategies that are optimal by matching those lower bounds. For each of our sorting strategies, we discuss the issues involved in implementing them on sub-bus machines. Finally, we empirically evaluate the performance of our sorting strategies by applying them to shearsort, a common two-dimensional mesh sorting algorithm. Our results suggest that for sorting the sub-bus broadcast capability gives only a slight advantage over using only nearest neighbor communication.

Citation:

James D. Fix and Richard E. Ladner. "Sorting by Parallel Insertion on a One-Dimensional Sub-Bus Array." IEEE Transactions on Computers, Volume 47, Number 11, pages 1267-1281.

On-line documents:

tech report version

Optimal "One-way" Sorting on a One-dimensional Sub-bus Array

Abstract:

This paper addresses the problem of sorting on a one-dimensional sub-bus array. We devise an abstract model of sub-bus sorting, characterized by parallel insertion operations applied to the data. The model captures the behavior of in-place sorting algorithms on real sub-bus machines like the Maspar MP-1.

Our results concentrate on a restricted class of sorting methods where all the communication operations occur in the same direction. For these one-way sorting strategies, the number of communication steps necessary to sort an input is exactly the maximum distance a value has to travel to its destination opposite the broadcast direction. We introduce the one-way greedy sorting strategies which match this lower bound tightly for our one-way model. The greedy strategies are not practical sub-bus algorithms, so we present adaptive insertion sort, an optimal one-way sorting strategy that is implementable on real sub-bus machines.

Citation:

James D. Fix and Richard E. Ladner. "Optimal One-way Sorting on a One-dimensional Sub-bus Array." In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. January 1995, pages 586-594.

also available as Department of Computer Science and Engineering Technical Report TR 94-11-01, University of Washington, 1994.

On-line documents:

Tech report version