RI: Large-Scale Dynamic Programming

在人工智能和计算机科学中，动态规划是一种非常通用、强大和健壮的问题解决范例。动态规划是一种算法模式，它包含了人工智能中许多著名的系统搜索算法，包括广度优先搜索、Dijkstra‘’S算法、马尔可夫决策过程的A*、值迭代和策略迭代，以及许多用于组合问题的多项式时间算法，以及用于数值NP完全问题的伪多项式时间算法。这些算法是非常健壮的，因为它们保证找到问题的解决方案(如果存在的话)，并且通常是最优解。大多数动态规划算法在它们可以解决的问题的大小方面受到可用存储量的限制。虽然半导体存储器的成本约为每GB 100美元，但磁盘存储的成本不到每GB 40美分，现在可以使用存储容量为1TB的单个磁盘。在实践中，使用多个磁盘可以将现代工作站上的可用存储空间增加三个数量级，而成本适中。不幸的是，在动态编程算法中，您不能简单地用磁盘存储替换内存。原因是，访问磁盘上的一个字节需要大约10毫秒，而主存大约需要100纳秒。但是，磁盘上的大数据块可以高速顺序读取或写入。这项工作将开发、实现和试验将数据存储在磁盘上的动态规划算法。主要的研究挑战是设计这些算法，使所有数据访问都是按顺序进行的。通过将资源瓶颈从空间转移到时间，将这些算法并行化以在多处理器或多核上运行成为额外的研究挑战。PI在这一模式上取得了一些成功，实现了大规模的广度优先和启发式搜索，一次运行几个月。这些技术将扩大到涵盖其他类别的动态规划算法。提出的挑战问题包括数值NP完全问题，各种问题空间的半径和直径的寻找，以及计算生物学中的氨基酸和DNA序列比对。如果成功，除了吸引加州大学洛杉矶分校的学生外，这项工作还可能对整个计算机科学产生影响。使用磁盘存储扩展内存的想法可能适用于任何内存密集型算法，并可用于通过提高缓存性能来加速完全驻留在内存中的计算。

Dynamic programming is a very general, powerful, and robust problem solving paradigm in artificial intelligence and computer science. Dynamic programming is an algorithm schema that includes a number of well-known systematic search algorithms in Artifical Intelligence, including breadth-first search, Dijkstra''s algorithm, A*, value iteration and policy iteration for Markov decision processes, as well as many polynomial-time algorithms for combinatorial problems, and pseudo-polynomial-time algorithms for numeric NP-complete problems. These algorithms are extremely robust, in that they are guaranteed to find a solution to a problem if one exists, and often an optimal solution.Most dynamic programming algorithms are limited in the size of problems they can solve by the amount of storage available. While semiconductor memory costs about $100 per gigabyte, magnetic disk storage costs less than 40 cents per gigabyte, and single disks with one terabyte of storage are now available. In practice, the available storage on a modern workstation can be increased by three orders of magnitude with multiple disks, at moderate cost. Unfortunately, you can''t simply replace memory with disk storage in a dynamic programming algorithm. The reason is that it takes about ten milliseconds to access a single byte on disk, compared to about 100 nanoseconds for main memory.However, large blocks of data on disk can be read or written sequentially at high speed. This work will develop, implement, and experiment with dynamic programming algorithms that store their data on magnetic disk. The main research challenge is to design these algorithms so that all data access is sequential. By shifting the resource bottleneck from space to time, parallelizing these algorithms to run on multiple processors or multiple cores becomes an additional research challenge. The PI has had some success with this paradigm, implementing large-scale breadth-first and heuristic searches that run for months at a time. The techniques will be broadened to cover other classes of dynamic programming algorithms. The proposed challenge problems include numeric NP-complete problems, finding the radius and diameter of various problem spaces, and amino acid and DNA sequence alignment in computational biology. If successful, in addition to engaging students at UCLA, the work can have impact throughout computer science. The idea of extending memory with disk storage is potentially applicable to any memory-intensive algorithm and can be used to speed up computations that reside entirely in memory by improving cache performance.