This is a companion for the synthesis lecture Optimization and Mathematical Modeling in Computer Architecture, which explores using Mixed Integer Linear Programming (MILP) to solve challenging problems in the field. The book gives in depth case studies of four optimization problems in computer architecture. This companion page provides a brief overview and live demo of the MILP formulation in all four case studies. We also provide a downloadable source package for each problem below.
Case Studies
Generating custom instruction candidates from an application is the process of analyzing the intermediate representation of the program, and finding subgraphs which can be made into instructions. Depending on the target system, these candidates must have certain properties in terms legality (including graph structure or node types), and should improve the performance as much as possible with respect to the software execution. The optimization problem we solve is to determine the convex set of operations inside a basic block, forming a custom instruction template, which maximizes the expected latency reduction.
Download GAMS CodeData-center resource managers are centralized software components which manage the execution of a large number of services. Since co-locating multiple services on the machine could degrade performance, it is critical that the resource manger effectively allocate machine resources. To perform this task adequately, the resource manager needs information about services and machines which can facilitate the mapping. The optimization problem we solve is to statically determine the best co-locations of services on servers such that the resource requirements and service level agreements can be satisfied.
Download GAMS Code
Hardware specialization has emerged as an important way to sustain performance improvements of microprocessors to address transistor energy efficiency challenges and general purpose processing's inefficiencies. The insight of many specialization techniques is to "map'' large regions of computation to the hardware, breaking away from instruction-by-instruction pipelined execution and instead adopting a spatial architecture paradigm. The optimization problem we solve is to schedule computation nodes (in a Directed Acyclic Graph) to the spatial architecture's ISA-exposed hardware resources.
Download GAMS CodeMany-core chip multiprocessors require multiple memory controllers to provide DRAM bandwidth, and must decide on which tiles they should be placed. This placement affects best-case latency and contention for network channels and routers. Also, the network fabric itself can be heterogeneous, and it must be decided where to place resources like buffers and virtual channels to minimize the congestion. This optimization problem is to determine both the memory controller placement and the heterogeneous network resource allocation.
Running Downloaded Code on NEOS
If GAMS is not installed on the system, NEOS can be used for optimization. First, download the client tools from NEOS Downloads. Then, when running a GAMS instance, enclose the GAMS source in between the following header and footer. This will make an xml file suitable for submitting NEOS jobs with the "NeosClient.py" python script.
model.xml
<MODEL_DESC>
<exampleName><MODEL_NAME></exampleName>
<category>milp</category>
<solver>Gurobi</solver>
<inputMethod>GAMS</inputMethod>
<model><![CDATA[
GAMS FILE TEXT
]]></MODEL_NAME>
</MODEL_DESC>
Note that the GAMS source must not use "include" or "batinclude" statements. Also, any externally generated output files will not be transmitted back to the user.
Finally, run the following command to submit the job:
NEOS_CLIENT_TOOLS/PythonClient/NeosClient.py model.xml
