In this demo, we solve a graph matching problem where a directed acyclic graph (DAG) is mapped onto an arbitrary graph. The DAG represents program instructions, and the graph represents a hardware substrate. Here, we consider four different architectures as our targets, TRIPS, DySER, and PLUG, as well as one “simple” architecture. The optimization goal is either to minimize the latency or throughput of the mapping. The figure below shows an example problem and solution.
Please see Chapter 5 of Optimization and Mathematical Modeling in Computer Architecture for details on the formulation of the scheduling problems.
Case Study 3:
Spatial Architecture Scheduling
Select an architecture (mouse-over for description).