Tutorials

Reversible Computing — Towards utilizing Nature's process for computing —

Kenichi Morita (Hiroshima University)

Physical reversibility is one of the fundamental microscopic laws of Nature. Since future computing devices will surely be implemented based on some physical phenomena of nano-scale level, it is an important problem how such properties of Nature can be effectively used in computing. Reversible computing is a paradigm where computing models are so defined that they reflect physical reversibility. In this tutorial, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. We shall see that, in reversible systems, computation can be often carried out very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible logic elements have computation-universality. We discuss these problems based on reversible logic elements/circuits, and reversible Turing machines.

Tetsuo Yokoyama (Nanzan University)

A reversible computing system has at any time at most a single previous computation state as well as a single next computation state. Reversible programming languages are designed to support for developing the reversible system. To guarantee their reversibility independently of the lower level architectures, reversible programming languages require unconventional language properties such as cleanness and no information destruction derived from reversible updates and explicit postcondition assertions. We discuss the fundamentals of reversible programming languages and criteria for their good design. As does every programming paradigm, we show that reversible programming has its own programming methodologies. The practicality of reversible programming languages is shown by implementation of a reversible fast Fourier transform and reversible physical simulation.

Katsunobu Imai (Hiroshima University)

A reversible cellular automaton (RCA) is a cellular automaton whose global function is injective and every configuration has at most one predecessor. Because reversibility is a physics-like constraint, RCAs are widely used as a modeling framework for physical phenomena such as ideal gases and fluids. In the viewpoint of the computational aspects, RCAs were thought to have limited computing power at first. But in spite of the constraints, RCAs turned out to have rich computing abilities such as computation-universality, self-reproducing ability, and so on. Thus RCA is studied as a model for nano-scaled or quantum computing devices because they are closely related to the physical constraints. In this tutorial, We briefly explain the basic properties of RCAs and research history. We also show the results about universal RCAs and self-reproducing RCAs as illustrations of computing and shape-forming abilities of RCAs.

Wei Sun (NEC)

The art of real-time task scheduling: terminologies, models and algorithms

As new services, architectures and technologies boom, more and more systems are designed to make responses in real-time, for example real-time search, real-time patient tracking and health care on the horizon. Researchers in traditionally non-real-time fields have to correctly understand and adopt real-time techniques from a large body of literature, in which multiprocessor scheduling has been intensively generated within recent two decades especially after modern multicore architecture came into being. Although today’s multiprocessors, very fast interconnection networks and shared memory architecture have weakened the concerns over the overhead from task migrations and preemptions, designers and practitioners are still needed to understand the trade-offs existing in multiprocessor real-time task scheduling. In this tutorial at first the art of real-time task scheduling will be addressed for correctly understanding the prospective of terminologies and models in real-time systems, and then the tutorial will focus on partitioned algorithms, global algorithms and their compromises oriented for good trade-offs. Moreover, some heuristics are also showcased for solving difficult real-time scheduling problems. The objective of this tutorial is to help designers and practitioners fast benefit the spectrum of real-time techniques.

Jacir L. Bordim (University of Brazilia)

Challenges and Opportunities in the Wireless Technology Arena

Over the years, transceiver device density has grown from a few devices per institution to the astonishing number of a few transceivers per user. Although such increase has a number of positive aspects and enabled new communication technologies, such as Bluetooth, WiFi, and others, making mobile computing a reality with thousands of users around the globe. However, the challenges that need to be dealt in other to accommodate the demand for future wireless based services is just beginning. Indeed, the questions regarding efficient means to efficiently manage spectrum allocation is up in the agenda in many countries. Driven by this, many researchers are taking a closer look into these issues. Opportunist spectrum sensing and spectrum allocation are among the areas that are being considered as a way to improve spectrum utilization without interfering with the licensing management schemes. These are some of the issues that need to be addresses in order to guarantee that the demand and new technologies and services will receive the necessary share of the spectrum. This talk will review some of the questions and challenges that are likely to be on the spot in the upcoming years in the wireless technology arena.