/ N. N. Mirenkov / Professor
/ S. G. Sedukhin / Professor
/ Gennady N. Erokhin / Visiting Professor
/ Shietung Peng / Associate Professor
Our general program is high-performance computing and advanced information infrastructure. We are also thinking about a planetary machine and active knowledge being developed by humanity. We are undertaking research efforts in parallel and distributed algorithms/architectures, visual (multimedia) languages and tools. We lead joint research projects "Communication-efficient parallel computing" and "A new paradigm for clustered computing". In the first research project, we focus on the design of communication-efficient parallel algorithms for Bulk-synchronous parallel computers. The key is to develop a router that can perform efficient point-to-point and collective communication among processors. The second research project will focus on modeling, developing software packages, investigating fault-tolerance and performance analysis for the clustered computing.
We are studying the problem of parallel program portability, skeleton-based techniques and developing the supporting tools. Our theoretical work is related to efficient algorithms for parallel numerical computation including linear algebra and Fourier transformation as well as for fault tolerant routing on certain interconnection networks, like hypercubes, star graphs, and torus. Information about our activities can be found on the laboratory Home Page: http://www.u-aizu.ac.jp/labs/sw-dpp/, which contains links to three experimental laboratory WWW servers. These servers hold the High-Performance Computing and Communication topics, on-line CD-ROM Digital Library and serve as mirror sites of, for instance, the "Computational Science Educational Project".
We are also studying the problem of high-performance terrain visualization and navigation using cluster of computers and three-dimensional rendering of high-resolution terrain models. In the frame of the project "Virtual Navigation in Aizu Region" a software package for transforming contours from geographical maps into digital elevation model was developed and an experimental Web server for Aizu Space Monitoring Center was established (http://asmc.u-aizu.ac.jp). Another Web server with clustered architecture was installed to support students activity in the area of high-performance clusters (http://typhoon.u-aizu.ac.jp).
As one of our results we would like to mention the S4CAD system. S4CAD (System of Systolic Structures Synthesis) is a high level interactive software tool for designing, analysis and modeling of systolic VLSI-oriented array processors. Starting with a localized data dependence graph of the algorithm S4CAD automatically produces all permissible array processors, among which the designer may chose the optimal one. World Wide Web page of the S4CAD is available at http://www-dpp.u-aizu.ac.jp/HPCC/S4CAD/.
The important question of our research is parallel program transparency and accessibility of massively parallel computers to large user populations. We are developing a multimedia technology for the interactive specification of application algorithms. This technology is related to visualization, animation and sonification of data processing methods. In fact, it is a 'filmification' of application algorithms. Each film is based on a rather big peace of knowledge of a class of the algorithms. Our approach is close to the idea of algorithmic skeletons (higher order functions). However, skeletons leave a big gap between reality and a human (a multi-channel being). So, we use algorithmic multimedia skeletons based on both mathematical and physical abstractions. Each film is a series of frames (computational steps) displaying one or more parameterized sets of nodes and/or moving objects in multi-dimensional space-time. Each frame highlights a subset of these nodes and/or moving objects. The films have their own sets of figures, sounds, colors and their own ``shape'' of the movement. Users recognize them due to a combination of all these features. Each film defines a partial order of scanning of the nodes or objects (and possibly, colors and sounds). As a rule, computation specified on different nodes (objects) of a frame is considered to be performed in parallel. Computation specified in different frames is performed sequentially. So, it is possible to say: the shorter film the better.
The user defines the specification by creating his new film. The corresponding program (sequential or parallel) is generated automatically. In fact, we are developing film machines where data, knowledge and algorithms (as well as results) are specified by films (self-explained components). Distributed film databases can be considered as active knowledge/software being developed by humanity. We lead two projects related to filmification of methods and data: Active Knowledge Studio and F-mail System for Elderly People and Handicaps (http://dpp6.u-aizu.ac.jp/).
Refereed Journal Papers
Filmification of methods is a programming technology based on special-purpose animations as units of a very high-level language. These units represent rather large pieces of knowledge about computational schemes. They are intuitively understandable and keep necessary level of mathematical rigor and accuracy. In this paper, frames of ``films'' related to the specification (programming) of cellular automation-like algorithms are considered. The explanation is provided for computation on image pixels where local substitution rules are used. Some details about representing features of algorithms in film names are considered, too.
We are developing a multimedia programming technology based on filmification of methods. Our films can be considered as a new format for data and knowledge representation. In this paper, films related to the specification of computation on trees are described. Micro-icons for editing and composing operations with films are also considered.
The design of array processors for solving linear system of equations using two-step division-free Gaussian elimination method is considered. The two-step method can be used to improve the systems based on the one-step method in terms of numerical stability as well as the requirements for high-precision. In spite of the rather complicated computations needed at each iteration of the two-step method, we develop an innovative parallel algorithm whose data dependency graph meets the requirements for regularity and locality. Then we derive two-dimensional array processors by adopting a systematic approach to investigate the set of all admissible solutions and obtain the optimal array processors under linear time-space scheduling. The array processors are optimal in terms of the number of processing elements used.
Refereed Proceeding Papers
A visual language to specify application problems and corresponding simulation techniques is considered. The idea behind the approach is making use of special-purpose animation ``films'' as communication units for computer-human dialog as well as units for data/knowledge acquisition. In fact, these films are a new set of multimedia signs. These signs are watchable, hearable, and executable. They combine features of animation clips with sounds and programs. Usually, a film is related to a parameterized set of nodes (and/or moving objects) in 4-D space-time and to a partial order of traversing the nodes. A set of nodes is a structure like a grid, tree, pyramid, multi-stage networks, etc. It can be also considered as an index space or a data structure. The variety of these sets is based on existing methods, possible structures in 3-D space, and structure compositions. This paper presents a visual language to develop such multimedia signs. The basis of the language is a set of micro-icons to specify different partial orders of 1-D structure scanning and compositions of these structures, as well as to create ``film'' formats and multimedia names (super-icons) for application methods.
A multimedia programming technology based on filmification of methods and data is presented. Within the framework of this technology software modules are created in a film format. This format is to support a new type of abstraction combining both mathematical and physical notions. Special operations on the modules to create new films are allowed. Films can be considered not only as building blocks, but also as multimedia signs with self-explanatory features, as well as large-grained units of data/knowledge representing some properties of real world objects/processes. So, databases of such films should become sources of active knowledge. In the paper we provide a brief overview of our approach, present examples of the film frames, describe modes to manipulate films and an icon language to create multimedia names of films. A special attention is paid to how computational formulas can be attached to a film (a multimedia algorithmic skeleton).
We describe techniques for a multimedia representation of matrix computations based on filmification of application methods and data. The multimedia representation is related to special-purpose pictures and animations rendering intermediate/final results of computation and schemes of corresponding computational methods. To support rendering data, a multimedia interface and matrix filtration and matrix scaling techniques are used. To support rendering computational schemes, a film technology is used. Within the framework of this technology, self-explained series of frames, an interface for formula attachment, a program management subsystem as well as tools for data manipulating are discussed.
In this paper the design of highly parallel array processors for computing multi-dimensional Discrete Fourier transform (DFT) is considered. We first present the design of three linear array processors for the 1-D DFT which are different in the ways that the I/O are handled. Then, we show how to use these linear array processors as building blocks to construct efficient array processors for the 2-D and the 3-D DFTs. The proposed array processors are highly parallel, scalable, and I/O efficient.
In this paper, the design of efficient array processors for computing multi-dimensional image transforms is considered. We introduce a new method, called dimensional splitting method, for the design of efficient array processors. First, linear array processors for one-dimensional image transforms with different I/O formats are constructed. Then these linear array processors are used as building blocks (bricks) for constructing array processors for multi-dimensional image transforms. This method can be applied to multi-dimensional image transforms with separable kernels such as discrete Fourier, discrete cosine, and Walsh-Hadamard transforms. We demonstrate the method by constructing array processors for multi-dimensional Walsh-Hadamard transform which has been widely used in many applications areas. We also propose a new design of linear array processors for one-dimensional Walsh-Hadamard transform, which improves the previous designs.
The volume contains papers as well as abstracts of Demo systems presented at the Second Aizu International Students Forum-Contest on multimedia (AIScontest99) being held in July 28-30, 1999 at the University of Aizu.
Academic Activities