Memoryless computation and network coding

近年来，随着迭代译码和空时码等多种技术的出现，信息论得到了长足的发展。这些已经在不同的现代通信标准中使用，从而表明信息理论提供了设计通信系统的最合适的方法。然而，它仍然面临着许多挑战，特别是它在不同领域的应用，如生物学、机器学习或复杂性理论。可以说，该领域最近的重大发展之一是网络编码，这是一种通过网络传输数据的革命性技术。与路由不同，网络编码允许中间节点组合它们接收到的消息，从而实现更高的吞吐量。路由将信息视为普通商品，而网络编码则充分利用信息的特殊性来传输数据。因此，在吞吐量、对网络拓扑变化的健壮性和数据包丢失方面，它可以显著优于路由。网络编码吸引了大量的研究，并激发了分布式存储和内容分发等其他应用。无内存计算是计算函数的新范式，它提供了两个主要的创新。首先，它以一种全新的方式计算函数。与将寄存器视为“黑盒子”的传统计算不同，无内存计算利用了这些寄存器中包含的信息的性质，并将不同寄存器的值组合在一起。因此，它可以看作是网络编码对计算的模拟。第二个创新在于计算模型，它提供了使用寄存器的任何可能的更新，而无需与内存通信。该模型旨在模拟在核心中进行的计算，因为它们主要涉及寄存器的操作。更新被看作是复杂性的量子化，因此复杂性度量是计算一个函数所需的更新次数，而不管每次更新有多复杂。从理论上讲，无内存计算比传统计算具有许多优点。首先，它在核心层面上提供了计算加速：对于某些函数类，我们可以获得比传统方法任意短的程序。其次，无内存计算不依赖于额外的缓冲区，因此可以在线执行计算。内存管理是一项繁琐的任务，它会显著降低计算速度；这对于具有共享内存的并行架构尤其重要。尽管可以通过使用不同级别的缓存来缓解这个问题，但它仍然使用更多的硬件并带来显著的开销。无内存计算提供了一个激进的替代方案：它根本不使用内存。因此，它通过防止内存冲突来简化不同任务的并发执行。它还优化了关键且昂贵的资源的使用，并通过避免与数据内存的任何通信提供了另一种加速。因此，无内存计算是一种创新的计算方法，具有很大的潜力来加速计算昂贵的问题和应用，包括多核架构和并行计算。无内存计算研究的长期目标是确定它比传统计算方法在哪些方面有优势，并构建能够充分受益于这些原理的硬件。所提出的研究是一项基础性工作，将为未来可能实现的无内存计算思想奠定必要的基础。特别是，我们旨在评估无内存计算提供的计算速度，设计有效的指令集和扩展现有框架以考虑并行线程。

Information theory has recently undergone a formidable development, with the emergence of diverse techniques including iterative decoding and space-time codes. These have been used in different modern communication standards, thus indicating that information theory provides the most appropriate approach to design communication systems. However, it still faces many challenges, notably its possible application to different fields, such as biology, machine learning or complexity theory.Arguably one of the recent great developments in the field is network coding, a revolutionary technique to transmit data through a network. Unlike routing, network coding lets the intermediate nodes combine the messages they receive, thus achieving a higher throughput. While routing treats information like an ordinary commodity, network coding transmits data by taking full advantage of the specific nature of information. As such, it can dramatically outperform routing in terms of throughput, robustness to network topology changes and packet losses. Network coding has attracted a large amount of research and has inspired other applications such as distributed storage and content distribution. Memoryless computation is a new paradigm for computing functions, which offers two main innovations. First, it computes functions in a radically novel way. Unlike traditional computing, which views the registers as "black boxes," memoryless computation takes advantage of the nature of the information contained in those registers and combines the values of the different registers. Thus, it can be seen as the analogue of network coding for computing. The second innovation lies in the computational model, which offers to use any possible update of a register, without communicating with the memory. This model aims at emulating computations as they are carried out in a core, for they mostly involve manipulations of registers. An update is viewed as a quantum of complexity, hence the complexity measure is the number of updates required to compute a function, regardless of how complex each update could be.Memoryless computation offers several advantages over traditional computing in theory. First, it offers a computational speed-up at the core level: for some classes of functions, we can obtain arbitrarily shorter programs than the traditional approach. Secondly, memoryless computation does not rely on additional buffers and hence performs computations in line. Memory management is a tedious task which can significantly slow down computations; this is particularly important for parallel architectures with shared memory. Although this problem can be alleviated by using different levels of cache, it still uses more hardware and brings a significant overhead. Memoryless computation offers a radical alternative: it uses no memory at all. It thus eases concurrent execution of different tasks by preventing memory conflicts. It also optimises the use of a crucial and expensive resource and offers another speed-up by avoiding any communication with the data memory.Therefore, memoryless computation is an innovative approach to computing, with high potential to speed up computationally expensive problems and applications including multicore architectures and parallel computing. The long term objective of research in memoryless computation is to determine where it could be advantageous over traditional means of computing and to build hardware which could fully benefit from those principles. The proposed research is fundamental work which will lay the necessary foundations for a possible future implementation of memoryless computation ideas. In particular, we aim at evaluating the computational speed-up offered by memoryless computation, designing efficient instruction sets and extending the existing framework to take parallel threads into account.