甲斐 宗徳

A remote memory paging system called a distributed large memory (DLM) has been developed, which uses remote-node memories in a cluster, as the main memory extension of a local node. The DLM is available for out-of-core processing, i.e., processing of large-size data that exceeds the main memory capacity in the local node. By using the DLM and memory servers, it is possible to run multi-Thread programs written in Open MP and pthread for large-scale problems on a computation node whose main memory capacity is smaller than the problem data size. A page swap protocol and its implementation are significant factors in the performance of remote memory paging systems. A current version of the DLM has a bottleneck in efficient page swapping because all communication managements between memory servers and the local computation node are allocated to one system thread. This paper proposes two new page swap protocols and implementations by introducing another new system thread to alleviate this situation. They are evaluated by a micro-benchmark, Stream benchmark, and a 7-point stencil computation program. As a result, the proposed protocol improves the performance degradation ratio, i.e., the performance using the DLM divided by the performance using only the local memory, from 57% in the former protocol to 78% in stencil computation, which processes data whose capacity is four times larger than the local memory capacity.

One of the key methods for the optimization of parallel processing in a program is task scheduling. This intends to minimize implementation time for the entire program by determining schedule for optimally allocating tasks, which are processing units comprising the program, to available processor elements into pieces. Due to complexity of calculation and being a large-scale problem, the optimization problem is extremely challenging to solve with the current algorithms in a practical amount of time. Authors studied the method of partially optimizing task graph as a technique of task scheduling for large-scale problems. This paper reports on scheduling method that supports hierarchical macro for task groups.

In our automatic parallelizing translator for sequential C programs with MPI, a set of all statements in a block scope is defined as a compound task. In this paper, at first, we implemented a parallelism analyzer for the inner levels of hierarchy of scopes in any compound task. By using this analyzer, we analyzed single loops and nested loops whose processing time may take the most of total processing time of a program in general. Although it seems that a loop has no parallelism at a glance, the loop may be restructured to have parallelism by eliminating data dependencies, called loop distribution. In addition, in order to reduce more processing time of for-loops, a code restructuring method, that has extract the efficiency of cache memory, has been implemented. These implementation result in reducing parallel processing time remarkably.

The authors of this study are using mobile agents with capability of strong migration to develop AgentSphere, a platform for an autonomous parallel and distributed processing system that significantly reduces loads of the complex execution control for its users. In AgentSpheres on a network, agents can migrate autonomously among PCs and execute their own processes. In this paper, we introduce two kind of securities for AgentSphere, one for the protection of agents and another for the protection of the resource of each PC from the attacks by agents sent onto it. In addition, we reconsider the file access mechanism on AgentSphere and implement a new file system in order to access files on any AgentSphere from any AgentSphere safely and transparently.

In our automatic parallelizing translator, an intermediate data structure based on parse tree of the sequential C program is generated. There are some analysis stages in our parallelizing translator, such as data dependency analysis stage, task granularity analysis stage, task scheduling stage, and parallel code generation stage. In this paper, we propose a new integration method of analysis result from each stage into the intermediate data structure based on parse tree for the purpose of translation efficiency. In addition, we report the implementation of the history mechanism of the translate-operations to the intermediate data structure based on parse tree in order to trace backward or forward of the sequence of the operations.

We have been studying an automatic parallelizing translator for sequential C programs with MPI, which is utilized by users without the knowledge for parallel programming languages and parallel computer architectures. In our parallelizing translator for C programs in the past, dynamic task execution control has been adopted for generated parallel programs, because it was difficult to analyze the costs of tasks, or execution time before actual execution. On the other hand, the researches on task scheduling technologies and task cost analysis has been evolved concurrently by another research groups in our laboratory and they are cooperating with the automatic parallelizing translator, so in this paper we report the implementation of generating parallel program with static task execution control and a tuning mechanism to reconfigure parallel programs by rescheduling with actual task execution time as task costs.

In order to implement high performance parallel processing, task scheduling is a very important key technology. However, task scheduling problems belong to very difficult optimizing problem and are not be able to solve in practical time. So, it is required to detect sub task graphs, which can be partially optimized independently, as soon as possible. Each sub task graph can be recognized as a macro task, therefore, total number of tasks will be reduced, and this results in reducing the time to solve scheduling problems. In this paper, we propose a new sub task graph detection mechanism which can find more sub task graphs. We show that some scheduling problems, which were impossible to solve by the conventional methods, can be solved.

In order to process the task-graphed parallel solution objects in a shortest time, task scheduling is important. Task scheduling is, however, a strong NP-hard combinatorial optimization problem, and therefore it is difficult to obtain optimal solution in a practical period of time with the task scheduling. For problems additionally extended to take inter-processor communication delay into consideration, it will be more time-consuming to obtain the optimal solution. For these problems, the authors perform parallelized optimal solution search based on branch and bound method. For the sake of effective and high-speed optimal solution search, it is necessary that the lowest limit of the process time from each task for bounding operation to the end of the final task be found out with consideration of the communication time between the tasks. In this study, we developed a method for improving the accuracy of the lower bound and a GUI tool for allowing to manually interfere the search order for the parallel search in order to find out better heuristics useful for the searching.

We the authors of this study use mobile agents with capability of strong migration to develop AgentSphere, a platform for an autonomous parallel and distributed processing system that significantly reduces loads of the complex execution control for its users. We have successfully executed the strong migration of agents on JVM by converting their source codes. However, there has been an issue that the overhead becomes larger accompanied by migration such as when saving or restoring the data in the stack area, or when migration to the resuming position occurs during the execution of the program. In order to improve this issue, a new mechanism for the strong migration using JavaFlow was built. We report that we also built the information sharing mechanism using a distributed hash table so both the user and the system can share information of each agent effectively.

AgentSphere is a platform for an autonomous parallel distributed processing system based on strong migration mobile agent system. In general, it is very difficult to manage load balance and effectiveness of total processing performance on parallel distributed processing system. Our approach is that mobile agents help us to perform effective parallel distributed processing by agents' autonomy. In our conventional AgentSphere, one has to describe all of agent's code necessary to functions of it by oneself. In this paper, we propose a mechanism for creating a new agent by using various functional agents, which have been prepared on the AgentSphere network a priori. According to this mechanism, when a user describe an agent's source code, one can write it easily and effectively without writing all of its code by means of selecting existing functional agents and delegating them to process the parts of functions.

Recently, the necessity for parallel programming has been increased with the rapid spread of multicore/multiprocessor systems. However, it is difficult for a programmer to create a highly-effective and high-performance parallel program. So, we are developing the automatic translator from C programs to parallel programs using MPI(Message Passing Interface). In our conventional automatic parallelism analysis of C program with pointer variables, it was able to analyze the data dependencies of only the pointer variables declared explicitly in the code. In this research, we have first applied the Shape analysis to C programs with pointer variables for getting to know the form of the recursive data structures which will be allocated and constructed dynamically at the time of execution. Then, using the result of the analysis, we can analyze the data dependencies of recursive data structures, such as linked list or binary tree structures, and detect more parallelism from C program.

In development of software which become larger-scale and more complicated every year, the importance of software test grows more and more. However, some domains where it is difficult to apply any software test exist. One of such domains is a GUI test. In order to conduct a GUI test, the method of "preparation of the complicated test code in con-sideration of various states", "the software test in manual operation", and "automating using expensive software" is taken. Since those methods are very high-cost, the method of describing a software test easily is desired. However, it is generally difficult to test to all the software containing GUI at the runtime. Then, in this paper, we propose runtime test approach for scenario branch applications with screen transitions like ATM screen or software installers. Proposed method can conduct software test for such specific applications easily and at low cost. It is also shown that most performance degradation by applying the proposed method to actual applications cannot be found.

In the AgentSphere network where a network situation is always changed, it becomes an important subject to perform parallel distributed processing using a number suitable for efficient behavior of the whole system of agents. In order that AgentSphere might make the cooperative behavior by agents efficient, a set of agents were generated by using AgentPool. In AgentPool, the user had to specify the number of agents to be generated, and it is fixed under their execution period. So, in this paper, the control mechanism of AgentPool was improved to change the number of agents dynamically, such that as the resource with which agents can work increased, the number of agents increased, and as the resource decreased, the number of agents decreased. Our proposed method not only makes resource requirements reasonable, but is useful for power consumption reduction of the whole system.

In recent years, since it seems that speed up of single processor or single core has been going up to the utmost physical limit, parallel processing by multicore or multiprocessor becomes the mainstream to make the processing speed much higher. On the other hand, developing the effectively parallelized programs is very difficult for software developers. So, it is expected that automatic parallelization of existing sequential programs is accomplished. In this paper, we propose a parallelism analysis method to find parallel structures from original sequential programs, and implement its dynamic parallel execution method for automatically parallelized C programs.

Since the task scheduling problems in the multiprocessor environments belong to the class of strong NP hard combinatorial optimization problem, the depth first search algorithms based on branch and bound(B&B) method are most effective to find an optimal solution. In order to reduce the search time with B&B method, it is the most important key to construct search algorithms with the way to bound many branches in the search space by more accurate lower bounds. However, it seems that there are no algorithms to create such lower bounds with consideration of processing system environments. In this paper, we propose three algorithms to create the lower bounds with consideration of number of processors, the lower bounds with consideration of processing time of successive tasks, and the lower bounds re-calculated in search process. Our experiments show that these algorithms give more accurate lower bounds and improve efficiency of search.

AgentSphere has been developed as an autonomous application framework for the heterogeneous parallel and distributed processing environment. AgentSphere runs on each machine, and provides a work field to mobile agents. As both AgentSpere and mobile agent are written in Java, there is a multithreading overhead problem in the case that application with very high parallelism is distributed onto fewer physical processing elements. So JavaVM has introduced Concurrent Utilities and ThreadPool for this problem, but they can work on only one JavaVM. In our research, we have developed AgentPool, which is similar to ThreadPool but available on multiple JavaVMs. We also report results of parallel processing of solving NQueens problem to show the performance of Agentpool.

Task scheduling is one of core technologies to improve the efficiency of parallel processing. A schedule is a solution of task scheduling problem, and make to cooperate the performance of parallel machines. The shorter length of schedule (makespan) is reduced, the more efficient parallel machines run. But, task scheduling problem is combinatorial optimization problem that has strongly NP hard computational complexity. Accordingly, it is necessary that to design algorithm taking account of more unforeseeable disposition in order to reduce makespan. Concerning to solve the problem, the disposition is considered with communication overhead between machines. In this paper, the authors propose new heuristic algorithms to optimize communication overhead. These are applied the focus to critical path of dependences and earliest allocation pattern of communications. The authors describe characteristics and processes of these algorithms, and our experiments show the effectiveness of them

In a heterogeneous processing environment in a computer network where multiple PCs running JavaVM on them are connected to, it is very useful to make any class instance movable among any PCs. However, JavaVM can't inherently load and execute unknown classes dynamically which are not in the class path specified at startup of the JavaVM. In this research, we propose and develop a new mechanism to recognize and execute any unknown class dynamically by implementing a multi-tiered classloader, special object stream and dispatch mechanism for transferred objects. This proposed technology is useful and indispensable component technology for parallel distributed processing system based on mobile agent system with strong migration mobility. This technology makes it possible to implement various non-stop software services.

The task scheduling problems belong to the class of NP complete or strong NP complete combinatorial optimization problem. Taking account of communication overhead into task graphs makes these problems more difficult to solve by depth first search algorithm based on branch and bound method because the search space becomes much larger. In this paper, we propose an extended version of original priority levels used in Critical Path Method. The calculation of more accurate priority level of each task taking account of communication time among tasks requires by itself to solve another combinatorial optimization problem. So, our proposed new heuristic calculation method of each accurate priority level is completed in practically short time. By using our newly proposed priority level for both heuristics and bound operations in the search, it is shown that the scheduling time become shorter than the branch and bound search with the original priority level.

The electronic states of manganese and lanthanide elements in SrGa 2S4 are calculated by the relativistic discrete varia-tional Xα method using a FORTRAN program of DVSCATR in order to investigate the mechanism allowing the 3d-3d transition of Mn in SrGa 2S4 by co-doping a lanthanide element. We use a spherical cluster model of the D2 symmetry which consists of 45 atoms of Sr9Ga12S24, representing SrGa2S 4, in our calculation. Doping a lanthanide to SrGa2S 4 is represented by substituting a Sr atom with a lanthanide atom (indicated by 'Ln') at the cluster centre as (LnSr8)Ga 12S24. Two types of co-doping models are prepared as (LnMn2Sr6)Ga12S24 for Mn Sr and (LnSr8)(Mn4Ga8)S24 for MnGa with keeping the D2 symmetry. As a result of the self-consistent charge (SCC) calculation, the averaged distance between a lanthanide atom at the cluster centre and surrounding eight sulphur atoms has to be set as 70 to 80% of that between the original Sr-S combinations. Calculated electronic states show that the Ln(5d) and Mn(4s, 4p) atomic orbitals are highly mixed, and in the lower energy range, the Mn(4s, 4p) and Mn(3d) are also highly mixed. This hybridization cascade can explain the co-doping effect as that the electrons optically excited to the unoccupied states relating to the Ln(5d) would finaly relax to the 3d-3d transition of Mn. © 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

Authors have developed a strong migration mobile agent system using Java. In order to make strong migration possible on usual JVM, we have already proposed an automatic code transformation method for such agents In this paper, in order to apply this strong migration mobile agent system to autonomic distributed processing, the system, called AgentSphere, which offers the space where agents can be active is proposed. Agents can perform their processing by entering into AgentSphere on any machine. AgentSphere consists of the core systems and the subsystems which support an agent's activities. As some of the core systems, a class loader which updates class files dynamically with agents' migration and the communication facility among AgentSpheres are designed and implemented. Moreover, as one of the subsystems, a virtual file system for autonomic distributed processing is implemented using out mobile agents.

The authors have been developing a strong migration mobile agent system in Java. Using the system, we are developing the platform of an autonomic distributed processing system, called AgentSphere. In this research, a mechanism so that an agent can create a backup of itself which includes data in the middle of execution is implemented. In order to use this mechanism, a user describes backup commands in the agent's code. The backed-up agent is sent into other AgentSphere. And when an original agent stops according to an unexpected situation, the backed-up agent will start its activity instead of original one in order to resume its processing. Moreover, the method to insert backup commands automatically in suitable positions of an agent's code is proposed. Furthermore, this paper also describes the implementation of a scheduler which performs initial distribution of agents and the communication functions between agents in AgentSphere.

The Distributed Large Memory system, DLM, was designed to provide a larger size of memory beyond that of local physical memory by using remote memory distributed over cluster nodes. The original DLM adopted a low cost page replacement algorithm which selects an evicted page in address order. In the DLM, the remote page swapping is the most critical in performance. For more efficient swap-out page selection, we propose a new page replacement algorithm which pays attention to swap-in history. The LRU and other algorithms which use the memory access history generate more overhead for user-level software to record memory accesses. On the other hand, using swap-in history generates little costs. According to our performance evaluation, the new algorithm reduces the number of the remote swapping in the maximum by 32% and gains 2.7 times higher performance in real application, Cluster3.0. In this paper, we describe the design of the new page replacement algorithm and evaluate performances in several applications, including NAB and HimenoBmk.

In order to keep high efficiency, high reliability, and fault tolerance in a distributed processing system, we have been developing an autonomic distributed processing system by using a Java-based mobile agent system. Since we used a mobile agent system based on a weak migration mobility in our system, it was difficult for users to write an agent program freely which can resume its process on destination computer from the point at which it stopped just before moving. In this paper, we propose a new source code transformation method for any strong migration mobile agent code. The method can transform the source code, which is easy to write for users, into the code to be executed on the ordinary JavaVMs(Java Virtual Machines).

The electronic states of lanthanide (Ln) atoms doped into the ternary thiogallate CaGa2S4 are investigated from the relativistic first principle calculations by the discrete variational X alpha method (relativistic DV-X alpha) on LnCa(8)Ga(12)S(24) spherical clusters. In view of the self-consistent charge (SCC) convergence, atomic coordinates in the cluster are optimized. As the result, a certain lattice contraction is locally induced around the Ln(Ca) substitution by more than 30% in maximum. The 4f orbitals of the Ln atom are not electronically isolated but form many molecular orbitals mainly hybridized with valence orbitals of the surrounding S and the second nearest Ga atoms. The LS coupling of the 4f orbitals does not always result in the discrete level splitting as the j = 5/2 and 7/2 states. Both of these states are partially degenerated to make some molecular orbitals. (c) 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

According to dynamic changes of a system, an autonomic distributed processing system can automatically distribute tasks efficiently, and can reissue the lost task. The mobile agent is suitable in order to realize such a system. In this research, the function of the mobile agent system, AgentSpace, was extended and used. The agents to support processing user tasks efficiently have been implemented. For evaluation of our system, SPMD-type multithreaded program of traveling sales-person problem in case of 13 cities was used, and as a result of executing by four heterogeneous PCs, as compared with the time of executing by one PC, the processing time was shortened to about 35.5% on the average.

初学者がプログラミングを学習する場合,一般に,最初は簡単な概念を学び,次第に高度な概念を習得するという順序を踏む.学習環境も,その進行に沿ったものが用意できるとよい.最初は,難しい概念を知らなくても使える取っ付きやすい言語や環境を与え,学習が進むに従って,高度な概念も扱えるJavaなどの実用的な言語へ移行させるとよい.これによって,初学者にプログラミングに対する興味を持たせ,学習意欲を継続させることが可能であると考えられる.そこで,プログラミング学習の導入部において用いるのに適した言語Nigariとその環境を開発した. Nigariの言語仕様は,Javaのそれを簡素化したものになっており,クラスやメソッドの宣言など,初学者にとって理解が難しいものを書く必要がない.一方,基本的な制御構造などは. Javaとぽとんど同じ仕様である.Nigariの実行環境は,オブジェクトを自動的に可視化する機能を持つ.これによって,学習者のプログラミングヘの意欲を向上させるだけでなく,オブジェクトの概念をも理解させることができる.早稲田大学コンピュータ・ネットワークエ学科1年前期のプログラミングの授業を実験の場とした.この授業は本来Javaを用いて実習を行うが,導入部にNigariを用いた.実験では,オブジェクトの可視化機能について学生から高い評価を得られた.また,言語を簡素にすることについても,ある程度の評価を得られた.

Priority levels with communication overhead and parallelized search for the optimal/sub-optimal solutions of task scheduling problem were proposed. Priority levels were used to determine the order of ready tasks to be allocated onto idle processors. Branching point in the serach was limited to the presence of tasks with the same priority level to terminate the search within a practical processing time. Results indicated a reduction in scheduling lengths by 15% and search processing time by 60% with 7 processors.