Michael D. Moffitt
Research Areas
Authored Publications
Sort By
MiniMalloc: A Lightweight Memory Allocator for Hardware-Accelerated Machine Learning
Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '23), 4 (2023), pp. 238-252
Preview abstract
We present a new approach to static memory allocation, a key problem that arises in the compilation of machine learning models onto the resources of a specialized hardware accelerator. Our methodology involves a recursive depth-first search that limits exploration to a special class of canonical solutions, dramatically reducing the size of the search space. We also develop a spatial inference technique that exploits this special structure by pruning unpromising partial assignments and backtracking more effectively than otherwise possible. Finally, we introduce a new mechanism capable of detecting and eliminating dominated solutions from consideration. Empirical results demonstrate orders of magnitude improvement in performance as compared to the previous state-of-the-art on many benchmarks, as well as a substantial reduction in library size.
View details
Search Strategies for Topological Network Optimization
Proceedings of the AAAI Conference on Artificial Intelligence, 36(9) (2022), pp. 10299-10308
Preview abstract
We consider an application of combinatorial search to the optimization of topologies in series-parallel networks. We propose a recursive search over the space of decomposition trees, in which partial solutions are obtained by exploring k-way partitionings of expandable nodes. We present two complementary pruning techniques that bound the value of intermediate solutions from above and below, applying monotonic operations to the contents of unresolved leaves. We also develop a means to exploit the convexity of our objective function, so as to prevent the redundant recomputation of subcircuit configurations. Finally, we evaluate our approach on a parameterized benchmark suite of electrical circuits, demonstrating over an order of magnitude improvement in performance as compared to a baseline implementation.
View details
Preview abstract
The NP-hard number-partitioning problem is to separate a multiset S of n positive integers into k subsets such that the largest sum of the integers assigned to any subset is minimized. The classic application is scheduling a set of n jobs with different runtimes on k identical machines such that the makespan, the elapsed time to complete the schedule, is minimized. The two-way number-partitioning decision problem is one of the original 21 problems that Richard Karp proved NP-complete. It is also one of Garey and Johnson’s six fundamental NP-complete problems and the only one based on numbers.
This article explores algorithms for solving multi-way number-partitioning problems optimally. We explore previous algorithms as well as our own algorithms, which fall into three categories: sequential number partitioning (SNP), a branch-and-bound algorithm; binary-search improved bin completion (BSIBC), a bin-packing algorithm; and cached iterative weakening (CIW), an iterative weakening algorithm. We show experimentally that, for large random numbers, SNP and CIW are state-of-the-art algorithms depending on the values of n and k. Both algorithms outperform the previous state of the art by up to seven orders of magnitude in terms of runtime.
View details
