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

这项研究涉及发现和开发可扩展的算法，用于解决工程中经常出现的困难计算问题。特别是，研究人员观察到，人造文物具有先天的结构，使这些文物易于设计，合成和验证独立于其绝对大小。人工制品，如互联网、集成电路芯片和大型分布式软件系统，继续以惊人的速度增长。处理这样的伪像的算法（例如，搜索互联网、合成集成电路或验证软件系统的正确性），但却不知道它们的内在结构和规律性，无法科普它们不断增加的复杂性。另一方面，可伸缩算法识别并利用它们操纵的对象的结构和规律性，以降低计算复杂性。因此，可扩展算法的研究和开发对于在快速变化的技术世界中保持进步至关重要。尽管在设计、合成和验证人类工程物体中使用的许多计算任务是最坏情况下的NP-难，但这些物体的复杂性不断增加，并且经常被制造和部署。众所周知的例子包括从机组人员调度到微处理器验证和现场可编程门阵列的路由，但问题实例的复杂性往往违背现代解决方法。知识产权的重用并不总是意味着将计算问题实例减少到更小的实例，即使应用这种减少，它们也可能导致次优。解决大规模困难问题的能力对于前沿计算机硬件的设计至关重要，随着硅光刻技术（EUV、X射线、电子束等）的进步，实例大小将迅速增加，纳米制造（分子电子学）和集成复杂性（片上系统）。因此，解决主流NP完全问题的经验改进对于信息技术复杂性的持续增长至关重要。该项目旨在通过智能利用问题结构来显着扩展实际算法的性能范围，以处理非常大的困难问题实例。研究人员正在追求这一目标，通过通用的和基本的结果，适用性超出目前流行的最坏情况的界限，是在与经验观察到的性能。

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.