ALCHEMY group: chaos governing computers?

[Date: 2005-07-18]

http://www.gelato.org/community/view_announce.php?id=10_64

One might think that the complex microchips that govern modern computers behave in a precise, predetermined way. For the members of the ALCHEMY research group at the French National Institute for Research in Computer Science and Control (INRIA), they behave in a chaotic, unpredictable way, comparable the weather.

Modern microprocessor architectures rely on impressive numbers of transistors: a commonly used Intel Pentium 4 microprocessor has 42 million transistors, while the more modern Itanium 2 has no fewer than 410 million. These units interact through intricate rules and 'their performance can be highly variable and difficult to predict', says Hugues Berry, member of the research team. According to the conclusions of the study, only chaos theory can explain this unpredictable behaviour.

In their research, the three members of the team analysed modern microprocessor performances by separately running the same standard programs many times on a simulator of the kind commonly used by engineers to design and test microprocessors.

They measured the time needed by the processor to perform the task and found that the time it took to execute the programs varied widely between different trials.

The ALCHEMY team noted that the performance of these microprocessors during the execution of certain programs displayed complex non-repetitive variations that challenge traditional analysis, but that have been successfully described using what is known as 'deterministic chaos' analysis.

Such complex behaviours are observed in many other systems, ranging from physics to biology and social sciences. One major example of such behaviour is the weather: even though we can precisely and mathematically describe the factors influencing the weather, it is nevertheless impossible to predict it accurately over long periods of time. Tiny changes in the initial data, such as temperature, wind speed or pressure can cause imply, later on, enormous variations.

For complex microprocessors, this means that the precise course of a computation, including how long it takes, is sensitive to the processor's state when the computation began.

This is the so-called 'butterfly effect', or more technically, 'sensitive dependence on initial conditions' - the essence of chaos. And this phenomenon, according to the ALCHEMY group's conclusions, is responsible for the erratic change in the speed at which some programs are executed.

For further information, please consult the following web address:
http://www.inria.fr/recherche/equipes/alchemy.en.html

Remarks: Peer reviewed publication and references:
'Chaos in computer performance'; Hugues Berry, Daniel Gracia, Olivier Temam. ALCHEMY group, INRA. Available at http://www.arxiv.org/nlin.AO/0506030

Category: Miscellaneous
Data Source Provider: INRIA (Institut national de recherche en informatique et en automatique)
Document Reference: Based on information from INRIA and press sources (New Scientist)
Programme or Service Acronym: MS-FR C
Subject Index : Information Processing, Information Systems; Mathematics, Statistics

RCN: 24160

CORDIS RTD-NEWS/© European Communities