ITR: Scalable Algorithms Enabled by Problem Structure and Applications to Computer Hardware

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

This research involves the discovery and development of scalable algorithms for solving hard computational problems that routinely arise in engineering. In particular, the investigators observe that man-made artifacts have innate structures that make those artifacts tractable for design, synthesis, and verification independent of their absolute size. Artifacts such as the Internet, integrated circuit chips, and large distributed software systems, continue to increase in size at a breath-taking pace. Algorithms that deal with such artifacts (e.g., searching the Internet, synthesizing integrated circuits, or verifying the correctness of software systems) but which are oblivious to their inherent structure and regularity are unable to cope with their ever-increasing complexity. Scalable algorithms, on the other hand, recognize, and take advantage of, the structure and regularity of the objects they manipulate in order to bring computational complexity down. The study and development of scalable algorithms, thus, is essential for maintaining progress in our fast-changing technological world. Despite the fact that many of the computational tasks employed in designing, synthesizing, and verifying human-engineered objects are worst-case NP-hard, such objects continue to increase in complexity and are routinely made and deployed. Well-known examples range from aircraft crew scheduling to microprocessor verification and the routing of field-programmable gate arrays, yet the sheer complexity of problem instances often defies modern solution methods. Reuse of intellectual property does not always imply reductions of computational problem instances to smaller ones, and even when such reductions are applied they may lead to sub-optimality's. The ability to solve large instances of hard problems is critical to the design of leading-edge computer hardware, and instance size will increase rapidly with advances in silicon lithography (EUV, X-ray, electron beam, etc.), nano-manufacturing (molecular electronics) and integration complexity (system-on-a-chip). Therefore, empirical improvements in solving mainstream NP-complete problems are critical to sustained increase in sophistication of Information Technologies. This project aims at significantly extending the performance envelope of practical algorithms in order to handle very large hard problem instances through intelligent utilization of problem structure. The investigators are pursuing this goal through generic and fundamental results with applicability beyond currently popular worst-case bounds that are at variance with empirically observed performance.