Recent Papers by 

Domenico Talia

Note: Papers are in PostScript format. You may send me by e-mail your comments on them.

Cellular Automata + Parallel Computing = Computational Simulation

D. Talia

Abstract

In the latest years a novel method has been added in science to theory and laboratory experiments for studying and solving scientific problems. That method can be defined as computational simulation. Computational simulation is based on the use of computers for modeling and simulation of complex systems in science and engineering. According to this approach, a computer equipped with problem-solving software tools may represent a virtual laboratory where it is possible to build a model for a given problem and run it under different conditions. Parallel computers represent a class of computing architectures that might effectively support the computational simulation approach. In particular, parallel computers are well suited for implementing inherently parallel computing abstract models such as cellular automata. This paper describes how the combination of the cellular automata model with parallel computing techniques and systems can be very fruitful in supporting the computational simulation approach in science and engineering.

General Terms: Simulation, Performance, Programming.

Other Keywords: High-performance computing, parallel programming, cellular automata, simulation, scientific visualization.

Proc. 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics, Berlin, August 1997.

Knowledge Discovery e Data Mining: Concetti, Algoritmi e Sistemi (in italian)

C. Pizzuti and D. Talia

Abstract

Research and development work in the area of knowledge discovery and data mining concerns the study and definition of techniques,methods,and tools for the extraction of novel, useful and not explicitely available patterns from large volumes of data. Data mining techniques originated from the usage of statistical analysis and machine learning techniques for the mining of patterns from databases. In the last few years new techniques and algorithms have been designed. This report gives an introduction to algorithms and techniques for knowledge discovery and data mining in databases. Further, it describes few significant data mining systems. The goal is to give an introduction to data mining and show how the use of knowledge discovery and data mining techniques in databases might bring significant benefits for the intelligent analysis of large volumes of data.

General Terms: Database Management, Artificial Intelligence, Pattern recognition.

Other Keywords: data mining, knowledge discovery, databases, machine leraning, parallel processing.

Published in Rivista di Informatica.

Calcolo Parallelo e Sistemi Complessi per Realizzare Laboratori Artificiali (in italian)

D. Talia

Abstract

This technically accessible article introduces computational simulation by cellular automata. Computational simulation is based on the use of computers for modeling and simulation of complex systems in science and engineering. According to this approach, a computer equipped with problem-solving software tools may represent a virtual laboratory where it is possible to build a model for a given problem and run it under different conditions. Parallel computers represent a class of computing architectures that might effectively support the computational simulation approach. In particular, parallel computers are well suited for implementing inherently parallel computing abstract models such as cellular automata. This article has been written to address a broad-based audience and it describes by simple examples how the combination of the cellular automata model with parallel computing techniques and systems might be very fruitful in developing virtual labs to support computational simulation.

General Terms: Simulation, Performance, Programming.

Other Keywords: High-performance computing, parallel programming, cellular automata, simulation, scientific visualization.

Published in Sapere.

This paper describes the practical use of the CARPET language for programming three-dimensional models of the contamination of soils developed in the CABOTO project. In this paper, we intend to show how the CARPET language and the CAMEL environment can be used to implement the simulation of the contamination of soils developed in the CABOTO project funded by the PCI ESPRIT programme. Our approach here is to devote enough space for discussing algorithms details and programming issues that generally are not addressed and discussed in the majority of papers on CA modeling and simulation. Here we discuss in detail the design and programming of the soil contamination model by CARPET and present results in terms of accuracy and performance of the simulation model on a MIMD parallel architecture.

General Terms: Languages, Performance, Programming.

Other Keywords: High-performance computing, parallel programming, cellular automata, simulation, scientific visualization.

Future Generation Computer Systems, North-Holland, vol. 13, no. 4-5, pp. 291-302, 1998.

This paper presents CARPET, a high-level parallel programming language based on the cellular automata model. CARPET is the language used for programming cellular algorithms in the CAMEL environment. CAMEL is an environment designed to support the development high performance applications in science and engineering. It offers the computing power of a highly parallel computer, hiding the architecture issues from a user. The system can be used both as a tool to model dynamic complex phenomena and as a computational model for parallel processing. By CARPET a user might write programs to describe the actions of thousands of simple active agents interacting locally, then the run-time system and the user interface allows a user to observe the global complex evolution that arises from all the local interactions.

General Terms: Languages, Performance, Programming.

Other Keywords: Parallel computation, programming languages, cellular automata, MIMD.

Proceedings of the 2nd Int. Workshop on High-Level Programming Models and Supportive Environments HIPS'97, IEEE Computer Society Press, pp. 55-63, April 1997.

Models and Languages for Parallel Computation

D. B. Skillicorn and D. Talia

Abstract

We survey many parallel programming models and languages. We use six criteria to assess their suitability for realistic portable parallel programming, arguing that an ideal model should be easy to program, should have a software development methodology, should be architecture-independent, should be easy to understand, should be efficiently implementable, and should provide accurate information about the cost of programs. We consider programming models in six categories, depending on the level of abstraction they provide. Those that are very abstract conceal even the use of parallelism from the software. They make software easy to build and port, but efficiency is usually hard to achieve. At the other end of the spectrum, low-level models make all of the messy issues of parallel programming explicit (how many threads, how to place them, how to express communication, and how to schedule communication), so that software is hard to build and not very portable, but is usually efficient. Most recent models are near the center of this spectrum, exploring the best trade-offs between expressiveness and efficiency. However, there are models that are both abstract and able to be implemented efficiently, opening the prospect of parallelism as part of the mainstream of computing, rather than a high-performance backwater.

ACM Classification: D.1 Programming Techniques, C.4 Performance of Systems, D.3.2 Language Classifications.

General Terms: Languages, Performance, Theory.

Other Keywords: Parallel programming models, parallel programming languages, general-purpose parallel computation, taxonomy, software development methods, object-oriented languages, logic programming languages.

A revised version of this paper has been published in ACM Computing Surveys, June 1998.

As per ACM Interim Copyright Policies, the Final Definitive Version will be maintained by ACM via a link. Since this work is currently available from a non-ACM Server, we are required to display the following general notice regarding your obligations under the copyright laws.

The above document contained in this WWW Site is included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

This position paper suggests a realistic strategy that the parallel computing scientific community should follow towards practical general-purpose parallel computation. The proposed approach is based on high-level programming models that might represent unifying models for parallel computation.

Keywords: Parallel computation, general purpose models, parallel programming.

Communications of the ACM, vol. 40, no. 7, pp. 98-99, 1997.

As per ACM Interim Copyright Policies, the Final Definitive Version will be maintained by ACM via a link. Since this work is currently available from a non-ACM Server, we are required to display the following general notice regarding your obligations under the copyright laws.

The above document contained in this WWW Site is included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

CARPET: A Programming Language for Parallel Cellular Processing

G. Spezzano and D. Talia

Abstract

In this paper we describe CARPET, a parallel programming language based on the cellular automata model. CARPET is the language used for programming cellular algorithms in the CAMEL environment. CAMEL is an environment designed to support the development high performance applications in science and engineering. It offers the computing power of a highly parallel computer, hiding the architecture issues from a user. The system can be used both as a tool to model dynamic complex phenomena and as a computational model for parallel processing. By CARPET a user might write programs to describe the actions of thousands of simple active agents interacting locally, then the CAMEL system allows a user to observe the global complex evolution that arises from all the local interactions.

General Terms: Languages, Performance, Programming.

Other Keywords: Cellular automata, parallel processing, complex systems, computational science, parallel programming.

This paper appears in the Proceedings of the European School on Parallel Programming Environments for HPC '96, France, April 1996.

CAMEL: A Parallel Cellular Tool for Interactive Simulation and Modeling

S. Di Gregorio, R. Rongo, W. Spataro, G. Spezzano, D. Talia

Abstract

This paper describes CAMEL an interactive parallel environment based on cellular automata theory. CAMEL is a tool designed to support the development of high performance applications in science and engineering. It offers the computing power of a highly computer although hiding the architectural issues to a user. The system can be used both as a tool to model dynamic complex phenomena and as a computational model for parallel processing. CAMEL implements a cellular automaton as a SPMD (Single Program Multiple Data) program and includes a load balancing strategy to minimize time costs in case of not uniform intervals for transition steps. The paper presents also a set of solutions in significant application areas such as lava flow, landslide, freeway traffic, genetic algorithms, and image processing where CAMEL has been successfully utilized to solve real complex problems.

General Terms: Simulation, Performance, Programming.

Other Keywords: Cellular automata, parallel computing, complex systems, computational science, parallel programming, SPMD.

Here you can find the HTML file.

IEEE Computational Science & Engineering, Vol. 3, No. 3, Fall 1996.