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.