/ N. N. Mirenkov / Professor
/ S. G. Sedukhin / Professor
/ Shietung Peng / Associate Professor
/ Alexander Vazhenin / Visiting 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".
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. Each film itself is considered as a special-purpose application for which a parallel program is developed in advance as an item of the system library. The specification of a problem is considered as input data for such a parallel program. However, this data can introduce a composition of a few films, an irregularity of computation, special sizes of data, etc. So, each film is supported at least by a few parallel programs from the system library. Different programs are related to different conditions being defined by the specification. In other words, a film has a special space of decision-making. This space takes into account levels of problem granularity, irregularity, dynamics of the data decomposition, and some others related to algorithm features. In fact, we are developing film machines where data, knowledge and algorithms (as well as results) are specified by films. Distributed film databases can be considered as active common 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.
Refereed Journal Papers
This paper describes a project of a massively parallel system related to Aizu's multimedia center. The system employs a highly parallel MIMD architecture using a conflict-free communication system as well as special-purpose units for graphic\&sound processing and image buffering which support high-speed input-output operations. The scalable communication system is comprised by a few networks using electronic and optical links. The idea behind the project software is making use of animation films as communication units for computer-human dialog. Each film is related to series of frames (computational steps) and reflects some knowledge about data processing. Each frame highlights a substructure of data for which operations should be specified. As a rule, this substructure is a set of points and/or moving objects in a multi-dimensional space-time.
The design of array processors for solving linear systems 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 is optimal in terms of the number of processing elements used.
The design of array processors for solving linear systems 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 is optimal in terms of the number of processing elements used.
Refereed Proceeding Papers
A multimedia technology to specify application problems and corresponding simulation techniques is presented. The idea behind the approach is making use of special-purpose animation (and video) 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/video clips with sounds and programs. As a result, conventional computers should become film machines. The paper presents basic ideas, methods and techniques for the implementation of this technology, describes a film management system and an approach to program synthesis.
We are developing a multimedia programming technology to specify application problems in a format of special-purpose animation films. According to this technology users should employ a new set of multimedia signs. These signs are watch-able, hear-able, and executable. They combine features of animation clips with sounds and programs. In this paper we describe a film (a multimedia sign) as a series of frames related to computational schemes for solving the linear algebraic systems. We also present a special form to be filled out by users for the specification of computation on nodes of a 2-D structure, as well as template programs and files to support automatic synthesis of programs from the film specification.
TOPAS (Test and Optimization of Parallel Algorithms and Structures), a programming tool for visualization, animation and investigation of algorithms of mapping graphs is presented. The tool is implemented in Java and can be accessible on WWW. Keywords: parallel algorithms, mapping, multicomputer system, visualization of methods, Java, network technologies, programming environment.
We are developing a new programming technology based on filmification of methods. In this paper we describe a film to be used for the specification of algorithms of the Depth Search Machine type. Some details of program synthesis from the film specifification are also considered.
The paper presents a special-purpose animation film related to basic computational schemes on pyramids. The film shows a partial order of the node traversal on a top-less quad pyramid. Frames of the film reflect a layer-by-layer technique of the computation. The user can employ it to specify his algorithmic ideas. A template control file and a template program supporting the code synthesis from film specifications are also considered. In addition, a taxonomy of pyramid shapes and layer traversals to show other types of the pyramid films are presented.
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 this paper, we present a model for cluster of computers which uses an arbitrage for partially decentralized control. Then, we derive formula for the coefficient of effective processing in different modes defined by the average number of communication requests in queue. Based on these formula and criteria data of the parametrs we investigate the performance of the cluster.
In this paper, parallel algorithm and application- specific array processors using division-free Gaussian elimination method are introduced. It is shown that the number of processing elements of initial design of array processor can be reduced on 2/3 by using pipelining approach. This approach is based on unlinear scheduling of computations.
Academic Activities