Software Development based on Continuous Computing Resources

为了能够构建能够处理计算机系统的广度和局部性的复杂性分析模型和软件系统，我们一直在基于连续计算资源的概念，从不同的角度重新审视、统一和发展现有的计算概念。本项目的主要成果如下：基于连续计算资源的复杂性分析：提出了一种计算模型，可以统一、简洁地表达从单台计算机的内存层次到计算机间网络延迟的各种计算概念。结果表明，基于该模型的复杂性分析结果比以前的模型更准确地反映了实际计算。为了更容易理解复杂并行算法的行为，我们设计了该模型的虚拟机，并实现了包括模拟器和可视化器在内的语言系统。并发语言模型LMNtal：我们设计了…More LMNtal（发音为“elemental”），一个基于层次图约简的并发计算的可扩展语言模型。在此模型上，我们建立了过程结构分析技术，并将该模型实现为现实和有用的编程语言。由于层次图约简包括多种计算模型，如多集重写模型和自组织模型，我们的结果有望成为现有计算模型之间的桥梁。基于局部性的语言实现：我们展示了通过关注局部性可以显著提高编程语言系统的运行时效率。一个典型的例子是通过使用基于“数据对象的分层聚类”的复制垃圾收集来提高局部性。该技术是通过进一步改进现有技术提出的，现有技术以深度优先顺序复制活动对象，使用较小的堆栈区域，并使用用于堆栈溢出的队列。这种技术不仅提高了虚拟内存中的局部性，而且提高了CPU缓存中的局部性，从而允许在真实计算机系统上实现高性能。少

In order to make it possible to construct complexity analysis models and software systems that can cope with both extent and locality of computer systems, we have been working to revisit, unify and develop existing computation concepts from various points of view, based on the notion of Continuous Computing Resources. The major outcomes of this project are the following.1. Complexity Analysis based on Continuous Computing Resource: We proposed a computation model that can uniformly and concisely express various concepts of computation from the memory hierarchy of a single computer to network delay among computers. We showed that complexity analysis results based on this model reflect real computation more precisely than previous models. In order to make it easier to understand the behavior of sophisticated parallel algorithms, we designed a virtual machine of the model and implemented language systems including simulators and visualizers.2. Concurrent Language Model LMNtal: We designed … More LMNTal (pronounced as "elemental"), a scalable language model for concurrent computation based on hierarchical graph reduction. On this model, we have established techniques for process structure analysis and implemented this model as realistic and useful programming languages. Since hierarchical graph reduction includes a variety of computation models such as multi-set rewriting models and self-organizing models, it is expected that our results will be useful as a bridge between existing computation models.3. Language Implementation based on Locality: We showed that runtime efficiency of programming language systems can be remarkably improved by focusing on locality. A typical example is the locality improvement by the use of copying garbage collection based on "hierarchical clustering of data objects". This technique is proposed by further improving the existing technique where live objects are copied in depth-first order, with a small stack area and additionally with a queue that is used in case of stack overflow. This technique improves not only the locality in the virtual memory, but also the locality in the CPU cache, and thus allows high performance implementations on real computer systems. Less