KR100800615B1 - Agent-based P2P-Message Passing Interface Middleware and Its Design Method - Google Patents

Abstract

The present invention relates to an agent-based P2P-MPI middleware that supports autonomous operation in a dynamic environment by applying MPI to a P2P-based distributed system and a design method thereof. In the method of designing agent-based P2P-MPI middleware of the present invention, the method of calculating the computational persistence ratio and the computational availability ratio of each resource provider is applied to the library, and the resource is calculated according to the computed computational persistence ratio and the computational availability ratio. Classifying providers and assigning each resource provider a unique identification key, and the coordinator applies an overlay network formation method to a library that forms a resource identification tree with other resource providers, and the same task It includes the process of applying the operation redundancy technique to the library which shortens the computation time by executing the job) simultaneously in several resource providers with low operation availability ratio and synthesizing these operations.

Grid Computing, MPI, P2P, Distributed Systems, Grouping, Resource Providers, Coordinators

Description

Agent-based P2P-message passing interface middleware and its design method {Agent P2P-MPI middleware and method for design the same}

1 and 2 are tables comparing the performance of conventional P2P based distributed systems.

3 is a flowchart illustrating an agent-based P2P-MPI middleware design process according to the present invention.

4 is a diagram illustrating a model of a P2P based distributed system.

5 is a diagram illustrating each resource provider classified according to a computation persistence ratio and a computation availability ratio according to the present invention.

6 is a diagram illustrating a state in which an identifier is assigned to each resource provider according to the present invention.

7 is a diagram illustrating a resource identification tree according to the present invention.

8 is a diagram illustrating an overlay network according to the present invention.

9 is a flowchart illustrating a process of applying the operation redundancy method according to the present invention.

10 is a diagram illustrating a 1: 1 operation dependency relationship according to the present invention.

11 is a diagram illustrating an n: 1 operation dependency relationship according to the present invention.

12 is a diagram illustrating a dependency graph according to an operation dependency relationship according to the present invention.

13 is a diagram showing the XML-encoded form according to the operation dependency relationship according to the present invention.

14 is a diagram illustrating a state in which each resource provider performs an operation according to an operation dependency relationship according to the present invention.

15 is a diagram illustrating an agent-based P2P-MPI middleware according to the present invention.

16 and 17 are tables comparing the performance of the conventional P2P-based distributed systems and the performance of the agent-based P2P-MPI middleware according to the present invention.

* Description of the symbols for the main parts of the drawings

S30: Calculation of computational persistence ratio and computational availability ratio for each resource provider

S32: Resource Provider Classification by Compute Persistence Rate and Compute Availability Rate

S34: Apply overlay network configuration method

S36: Apply Redundancy Technique S38: Apply Dependency Technique

40: Central Management Server 41: Client

42: storage server 43: resource provider

44: Adjuster

The present invention relates to an agent-based P2P-MPI middleware that supports autonomous operation in a dynamic environment by applying MPI to a P2P-based distributed system and a design method thereof.

Grid computing is a technology to maximize computing power and efficiency by integrating various computer resources by connecting computers to a network. Called The Grid, the virtual machine measures which computer's resources remain for a certain amount of time and concentrates on one task. In other words, it maximizes the resource efficiency between networked computers and speeds up work.

In the grid computing, a message passing interface (MPI) technology is applied. The MPI is a standard interface for application scientists to execute a parallel program on a high-performance computer and is a parallel processing middleware based on a message passing technique. . Every process that participates in an MPI application performs a specific task by exchanging messages with each other with its own ID (RANK). Therefore, every process should first grasp its role (RANK), the overall structure and the other party's position in the overall program. This is handled by the MPI_Init function, and the MPI application can be executed only when the MPI_Init process is completed. Existing applied scientists prefer to work with existing MPI code rather than creating applications with new interfaces in a grid environment.

An API for performing work using MPI middleware (library) in the grid environment is MPICH. The MPICH is implemented in consideration of high performance and portability and is most widely used among MPI standards. To date, MPICH-G2 and MPICH-P4 are known. The MPI initialization methods of MPICH-G2 and MPICH-P4 are both centralized, and the mediation process must be centrally located to continuously intervene in exchanging information. Therefore, if the location of the mediation process greatly affects performance, Depending on the type of mediation process, the dependence on middleware becomes very large.

On the other hand, P2P-based distributed system is a means to replace the application that was performed in the existing supercomputer, the research on the standard interface for the calculation for various scientific applications is actively being conducted. However, current P2P-based distributed system environment has limitations in performing various applications due to platform limitations. Although most applications have a single program multiple data (SPMD) type in a single program or multiple programs multiple data (MPMD) type in a multi-program, applications currently implemented in a P2P based distributed system system are single program. Is performed in the form of Single Program Single Data (SPSD). In addition, in the P2P-based distributed system environment, resource providers are dynamically and dynamically change their status by allowing them to freely join or leave their resources. In such a dynamic computing environment, in order to perform SPMD or MPMD applications with a large number of heterogeneous resources (resources providers), a stable computing environment must be provided and a standard interface technology for performing dependent computing is required.

 Therefore, it is classified into researches to ensure reliable computational performance to adapt to dynamic computing environment in P2P-based distributed computing environment and to apply MPI technology aiming at performing various applications. In other words, P2P-based distributed computing projects and project research combining MPI middleware technology in grid computing were conducted as follows.

1) BOINC: A platform that realizes distributed computing (public resource computing) by using voluntary participation of desktop resources, and provides computing space, and desktop owners divide and allocate their resources (CPU, disk-space) constantly Enable you to participate in the project.

2) JNGI: A Java-based framework that supports large-scale operations developed by Sun Microsystems, Inc., using JXTA protocol to support grouping and peer-to-peer communication of freely available and unsubscribed resources.

3) P3: A large-scale operation support middleware developed by AIST in Japan that supports JXTA protocol. It supports self-organizing, discovery, and grouping among peers. Members of P3 are divided into a host, which means a general resource provider, and a controller that manages participation, withdrawal, and performance of other resources.

4) P2P-MPI: Developed at the University of Louis Pasteur in France, it is a large-scale computing support middleware that supports self-configuration, data management, process robustness, and abstraction of computational power. P2P-MPI is basically implemented by three modules: Message Passing Daemon (MPD), File Transfer Service (FT), and Fault Detection Service (FD).

5) MPICH-V is a volatility tolerant MPI environment developed at the University of Paris-South Paris, France, to cope with node volatility such as node failure or network disconnection to perform SPMD or MPMD applications. In the MPICH-V, a rollback recovery method using an uncoordinated checkpoint and a distributed message logging method are used to show determinism and high fault tolerance for node volatility.

In the existing P2P-based distributed system environment, there is a problem that the operation execution method is unified without providing a stable operation execution environment because there is no operation grouping method or availability-based operation duplication method according to the availability of resource providers. Secondly, due to the limited application performance without dependence between operations, there are limitations in the performance of various applications and difficulties in commercialization and business model creation.

However, each P2P-based distributed system described above is still inadequate in application to resource provider availability-based grouping technique, availability-based redundancy technique, and P2P-based MPI technique for performing various applications. That is, as shown in FIGS. 1 and 2, each P2P-based distributed system does not produce a result that satisfies all in P2P-based MPI application, operation grouping, result inspection method, replication method, and availability-based copy number method. I can't.

In order to solve the above problems, the present invention is to develop a resource provider availability-based grouping technique to ensure a stable operation in a P2P-based distributed system environment, and to develop an algorithm for improving operation reliability through availability-based redundancy. We also propose agent-based P2P-MPI middleware, which is a standard interface for performing various applications.

In addition, it aims to propose a P2P-based distributed computing method used to design such agent-based P2P-MPI middleware.

After all, an object of the present invention is to propose a middleware that includes a library for a message passing library suitable for a P2P based distributed system and a library for agent-based autonomous operation.

In order to achieve the above object, the present invention provides an operation persistence ratio indicating how much time each resource provider has provided resources in a P2P distributed system, and an operation availability ratio indicating a probability that each resource provider participates in the operation. Generating a first library by applying the calculation method to the first library, classifying resource providers according to the calculated operation persistence ratio and operation availability ratio, and assigning a unique identification key to each resource provider, After selecting a resource provider with high performance of resource provider's operation persistence rate and operation availability ratio as coordinator, the coordinator applies the overlay network formation method of forming a resource identification tree with other resource providers to the library to create a second library. The same task The process of creating a third library by applying a task redundancy technique to a library by shortening the computation time by executing a task job simultaneously in multiple resource providers having a low operation availability ratio and synthesizing these operations, and each resource provider And generating a fourth library by XML encoding the operation dependency relationship so that a calculation group is formed around a coordinator dynamically according to operation dependency relationships between the two.

In addition, each resource provider and coordinator includes a process of generating an agent-based autonomous P2P-MPI operation module to apply the generated each library to the MPI.

수식에 의하여 산출하는 과정과, 동일한 연산 작업을 수행하는 상 기 연산중복 자원제공자들 중에서 해당 연산을 완료한 자원제공자가 있을 시에는 해당 연산결과를 다른 연산중복 자원제공자들에게 전송하는 과정과, 상기 연산결과를 수신한 연산중복 자원제공자는 해당 연산을 취소하고 상기 조정자로부터 다른 연산작업을 수령하는 과정과, 해당 연산그룹의 조정자는 모든 작업이 완료될 시에 그룹의 구성원인 연산중복 자원제공자들에게 작업완료 메시지를 전송하고, 상기 연산중복 자원제공자들은 해당 작업완료 시간을 저장하는 과정을 포함한다.In addition, the operation duplication method in the process of generating the third library, ψ _i is the predicted completion time performed by the resource provider i without the volatile feature, θ _t is the predicted completion in the state having a volatile feature at time t Time, Λ _i is the operation availability ratio of the resource provider i, and the number (n) of operation duplication resource providers that perform the same operation

A process of calculating according to a formula, and if there is a resource provider that completes the operation among the operation duplication resource providers performing the same operation, transmitting the operation result to other operation duplication resource providers; The operation duplication resource provider receiving the operation result cancels the operation and receives another operation from the coordinator, and the coordinator of the operation group is sent to the operation duplication resource providers who are members of the group when all operations are completed. The task completion message is transmitted, and the operation duplication resource providers include storing a corresponding task completion time.

In addition, the agent-based P2P-MPI middleware of the present invention, a P2P communication library for supporting P2P communication between resource providers in a P2P-based distributed system, an MPI library supporting a message passing interface (MPI) in a P2P-based distributed system, It supports calculation of operation availability ratio and operation persistence ratio, supports configuration of overlay network by assigning identifiers, and operation duplication technique that allows multiple resource providers to execute operations simultaneously to reduce computation time and between resource providers. Agent library that applies dependency method that shows operation dependency relationship, and coping with environment change in dynamic environment, autonomously creates duplicates according to the operation availability ratio of specific resource providers to perform duplicate operation, autonomous migration and continuous operation To ensure, the MPI library and agent It has an agent-based autonomous P2P-MPI operation module that has a function to call the library.

In addition, the P2P-based distributed computing method according to the present invention, the operation persistence ratio indicating how much time each resource provider in the P2P distributed system provided resources for a period of time, and the probability that each resource provider to participate in the operation Calculating resource availability ratios, classifying resource providers according to the calculated computed persistence ratios and computed availability ratios, assigning each resource provider a unique identification key, and calculating the computed sustainability ratios and computed availability. After selecting a high-performance resource provider as a coordinator, the coordinator forms a resource identification tree with other resource providers to form an overlay network, and performs the same task job with a low operation availability rate. Simultaneously run these operations on multiple resource providers By including the step of applying the computed redundant techniques to shorten the operation time.

Hereinafter, the detailed description of the preferred embodiments of the present invention will be described with reference to the accompanying drawings. In the following description of the reference numerals to the components of the drawings it should be noted that the same reference numerals as possible even if displayed on different drawings. In addition, in describing the present invention, when it is determined that a detailed description of a related known function or configuration may unnecessarily obscure the subject matter of the present invention, the detailed description thereof will be omitted.

We develop a reliability improvement algorithm based on resource provider availability for reliable operation in P2P based distributed system environment. Resource providers have the characteristic of volatility to withdraw from operations in the middle of performing them. Due to this feature, if a resource provider that is running in the middle of the application with dependencies between operations is withdrawn, the resources to be executed later are put in a waiting state for operation, which causes a delay in performing the entire operation. do. In order to avoid such a phenomenon, the present invention proposes an agent-based P2P-MPI middleware applying a grouping scheme according to resource provider availability, an algorithm for improving reliability of operations through availability-based redundancy, and a task description technique based on inter-operation dependencies. As a result, the present invention provides an environment capable of performing MPI application through stable and efficient resource and task management through the proposed technique in order to solve the unstable computing environment and difficulty of resource / task management of P2P based distributed system.

3 is a flowchart illustrating a process of designing an agent-based P2P-MPI middleware according to an embodiment of the present invention.

In order to design the agent-based P2P-MPI middleware according to the present invention, after generating a library (S32) classified based on the operation persistence ratio and the operation availability ratio (S30) for the resource provider, an overlay network for the resource providers is generated. After the constituent library design (S34) is made, a calculation redundancy method (S36) that simultaneously calculates a plurality of resource providers with a low computational availability ratio to shorten the calculation time and an operation dependency specifying operation dependency relationships between each resource provider. Library design should be made as a process of creating a description (S38) and generating a performance module that applies the MPI to the MPI (S40).

Referring to each of the above steps, first, a library generation process (S30) for supporting calculation of the computational persistence ratio and the computational availability ratio for resource providers will be described. For convenience of explanation of the process of calculating the computational persistence ratio and the computational availability ratio for resource providers, the appearance of resource providers in a P2P based distributed system is briefly shown in FIG.

The P2P-based distributed system is composed of a client, a central management server, a result server, a volunteer, and a coordinator. In the P2P-based distributed system, the central management server 40 performs a job distribution and result collection role, and the remaining roles are performed by the coordinator 44 to reduce a lot of load. In addition, unlike the centralized type, operation groups are formed dynamically around the coordinator 44, and each resource provider 43 communicates between them through P2P communication technology depending on the dependencies between operations. In addition, the coordinator 44 is an object that is selected from the resource providers 43 to play a role of coordination. According to a predetermined condition, the coordinator 44 binds the selected coordinator 44 and the resource providers 43 to form a grouping 45. Is done.

The central management server 40 calculates an operation persistence ratio and an operation availability ratio of each resource provider 43 in order to perform grouping as shown in FIG. 4, wherein the operation persistence ratio is a resource provider 43 participating in an operation. It refers to a number indicating how long resources are provided, and the computation availability ratio refers to the probability that the resource provider 43 can participate for a predetermined time.

Hereinafter, calculation defects, calculation persistence ratios, and calculation availability ratios will be defined and used for understanding of the present invention.

[Definition 1] computational failure; An operation defect means that a resource provider withdraws while performing an operation. In the P2P-based distributed system environment, all resource providers assume that computational faults can occur depending on the characteristics of volatility.

[Definition 2] computation time rate; The computational persistence rate indicates how much resources are provided by the provider on a daily basis (24 hours). This is consistent with the reliability for continuous computation. It is calculated | required by following formula (1).

[Definition 3] computation availability rate (Λ); The computation availability ratio is a factor that indicates the probability that an operation can be performed at time t, and this factor indicates the number of times a resource provider will leave during the operation. It is calculated | required by following formula (2).

[Equation 1]

Ξ (Operation Persistence Ratio) = 1-1 / λ

[Formula 2]

Λ (computation availability ratio) = MTTCF / (MTTCF-MTTCR)

In Equation 1, the parameter λ represents an operation withdrawal rate. In addition, Mean Time To Computation Failure (MTTCF) in Equation 2 refers to an average occurrence of an operation defect indicating how often the resource provider withdraws from the operation performed by the resource provider. Mean Time to Computation Repair (MTTCR) represents the average of the time that a resource provider participated in an operation.

After calculating the operation persistence ratio Ξ and the operation availability ratio Λ as described above (S30), the two parameters Ξ and Λ are classified into predetermined regions according to the performance of the resource provider (S32). This sorted view is shown in FIG. 5, where the availability ratio is located on the vertical side and the computational persistence ratio is located on the horizontal side, so that the resource provider 43 has a higher computational availability ratio and at the same time a higher computational persistence ratio, so that the LLV 52; It is located in the Long-Lived Volunteer area, and the higher the computational availability rate and the lower the computational persistence ratio, the lower the computational availability ratio and the higher the computational persistence ratio are. 54, it is located in the Free-Lived Volunteer area, and the lower the computational availability rate and the lower the computational persistence rate, the lower the TLV (Timeoff-Lived Volunteer) area.

For reference, as described above, an algorithm for classifying a resource provider according to an operation availability ratio and an operation persistence ratio may be programmed as follows.

var

Ξ // computation time rate

Λ // computation availability rate

Vi // property of volunteer i

volunteerClassification ()

while the number of V

if 0.8 <Ξ <1 and 0.5 <Λ then

Vi = LLV;

else if 0.5 <Ξ <0.8 and 0.5 <Λ then

Vi = HLV;

else if 0.3 <Ξ <0.5 and 0.0 <Λ <0.5 then

Vi = FLV;

else if 0.0 <Ξ <0.3 and 0.0 <Λ <0.5 then

Vi = TLV

endwhile

As shown in FIG. 5, the resource provider is classified into the HLV region 51, the LLV region 52, the TLV region 53, and the FLV region 54 according to the computation availability ratio and the computation persistence ratio. Resource providers in the LLV region 52 having a high persistence ratio are selected as coordinators 43.

On the other hand, after classifying the resource providers according to the operation availability ratio and the operation persistence ratio as described above (S32), an overlay network is formed based on this (S34), and the overlay network is stable and effective in the P2P-based distributed system. For discovery and management, as shown in FIG. 8, the coordinator and each resource provider are located at the global level and the local level to network. The overlay networking method is a method of calculating and configuring a hash distance using a hash function as a logical distance based on a response time between a start node and a resource provider. This configuration method is applied as a library of agent-based P2P-MPI middleware.

The process of forming the overlay network is performed as follows.

First, it has a hash step for the compute resource. The hash function for considering the logical locality of the operation resource provider allocates a unique identification key for the resource provider to construct a resource identification tree (RID-tree). Referring to FIG. 6, the identification keys of the resource providers include a bit as a Global Location IDentifier (GLID), b bit as a Local Location IDentifier (62), and an object identifier (OID). C bits as; Object IDentifier) and two bits as an Object Classification IDentifier (64).

That is, a global location identifier 61 (GLID) having a bit size to indicate that it is located in the global area, which is the upper level among the providers, and b bit size to indicate that it is located in the local area at the lower level, among the providers. The local location identifier 62 (LLID), the object identifier 63 (OID) having a c bit size to indicate the unique ID of the resource provider, and the object classification identifier having a 2-bit size to indicate the functional role of the resource provider. 64; OCID) is assigned as an identification key.

When a client entrusting an application sends a resource request message to a starting node (eg, a central management server), the starting node identifies the client's location via a global location identifier (GLID) and then sends a message to the coordinator. Every bit string consists of a, b, c and 2 bits. The size of the global region is 2 ^{a + b} and the size of the local region is (1/2) ^a . And the number of mediators are selected one by one, based on the respective local areas, i.e., arithmetic operations and the availability ratio in the operation group is the persistence ratio (1/2) ^a. The object identifier (OID) is calculated with a hash function, and the object classification identifier (OCID) is determined as follows. For example, if OCID is '00', it is a resource provider. If OCID is '01', it is a coordinator. If OCID is '10', it indicates a start node.

After allocating an identification key for a resource provider as shown in FIG. 6, a resource identification tree (RID-tree) is constructed. The resource identification tree (RID-tree) is generated by determining the height of the tree according to a region size as shown in FIG. Resource providers participate in the system and are assigned to groups according to logical distances to generate GLIDs and LLIDs according to random hash functions. Then, an agent is created and performed according to the characteristics of the resource provider.

Meanwhile, a coordinator-initiated overlay network (CONet) forms a logical network for resource providers in a multidimensional symmetric structure. That is, the size of the coordinator-based overlay network is dynamically configured at the global level and the local level according to the number of resource providers. In FIG. 8, the 2D coordinator-based overlay network according to the glover level and the local level is represented as described above. The global level serves as a coordinator as a higher level of the local level, and the local level serves as a mediator of a mediator of the coordinator at the higher global level.

As described above, when a resource provider wants to participate in the overlay network, it must register information such as a profile and an IP address with a start node. To this end, like the Salping Bar, the resource providers are classified into four groups (HLV, LLV, TLV, and FLV) according to the operation availability ratio and the operation persistence ratio, and then the start node calculates a logical distance based on the response time of the resource provider. The global position is determined and the local position is determined according to the random hash function.

After all, when a resource provider joins the overlay network, the P2P distribution system allocates appropriately to a predetermined coordination space in order to obtain a global level unique identifier (global identifier) and a local level random identifier (local identifier). The neighbor resource provider on the overlay network is searched to obtain the neighbor's global identifier, local identifier and IP address.

If a resource provider does not perform due to duplication in the group when leaving the system, the group coordinator selects a resource provider that can be performed in the group, and otherwise sends a resource request message to the neighbor coordinator. In addition, depending on the characteristics of the resource provider, it is possible to guarantee the persistence of the operation performed by the checkpoint method or the operation migration method.

On the other hand, when the overlay network is configured as described above (S34), in the case of the resource provider in the region having a low operation availability ratio, such as the TLV region 53, FLV region 54 of FIG. . This is because, in a P2P-based distributed system, the task completion time depends on the performance of individual resource providers participating in the calculation, in particular, the ratio of resource availability of the resource providers. In order to improve this, the agent-based P2P-MPI middleware of the present invention applies an operation duplication technique to the middleware to shorten the computation time after the grouping through the overlay network is completed (S36). That is, the same task job (task task) is executed simultaneously in a number of resource providers with low operation availability ratio to reduce the computation time by combining their operations.

The operation redundancy technique is a method of guaranteeing reliable operation and reducing the execution time of the entire operation by coping with operation defects of a resource provider. The agent-based P2P-MPI middleware of the present invention has a process of applying the operation redundancy technique. . The algorithm of the above-mentioned operation duplication method is shown in the flowchart of FIG.

Referring to FIG. 9, first, a process (S91) of calculating an operation duplication resource provider number n is performed. The calculation of the number of redundant resource providers (n) is based on Equation 3 below.

[Equation 3]

Where ψ _i represents the predicted completion time performed by the resource provider i without the volatile feature, θ _t represents the predicted completion time with the volatile feature at time t, and Λ _i is the computational availability of the resource provider i Indicates a ratio.

After calculating the operation duplication operator atom number n by [Equation 3] as described above, the same operation is performed to the calculated n operation duplication resource providers (S92). When any one of the redundant operation resource provider completes the operation (S93) with respect to the duplicated operation, first, the result of the completed resource provider is transmitted to another operation redundant resource provider (S94). After that, the job whose execution is completed is confirmed by canceling the job number, and requests the coordinator to perform another job and receives it (S95). The coordinator of the operation group transmits a task completion message to the members of the group when all tasks are completed (S96). Here, the resource provider stores the work completion time whenever the work is finished as shown in [Equation 4].

[Equation 4]

Θ _i denotes an average completion time for θ _i ^′ , which is a profile-based transfer completion time of resource provider i.

After the algorithm of the operation duplication method as shown in FIG. 9 is applied to the agent-based P2P-MPI middleware (S36), the dependency technique, which is a work technique technique using the inter-operation dependency, is applied to the agent-based P2P-MPI middleware (S38). .

Dependency technique through dependency between operations can be divided into two categories. First of all, if the operation S _j is executed in a dependency relationship between 1: 1 operations, S _i and S _j are 1: 1 dependencies if the operation is in a dependency relationship with S _i . Secondly, if there are no dependencies S _i , S _j of two nodes, but the two operations S _i , S _j have a dependency relationship with S _k , then S _i , S _j and S _k are n: 1 Classified as dependency relationship between operations.

The relationship between the 1: 1 operations is shown in [Definition 4] and FIG. 10, and the dependency relationship between the n: 1 operations is shown in [Definition 5] and FIG. 11.

[Definition 4] Dependency relationship between 1: 1 operations (FIG. 10)

로 표현된다.If the operation S _i , S _j of each resource provider is dependent on the operation S _i , S _j when operation S _j is previous (S _j )-> current (S _j ),

It is expressed as

[Definition 5] Dependency relationship between n: 1 operations (FIG. 11)

로 표현된다.If two nodes S _i and S _j have no dependence but previous (S _k )-> current (S _k ), if two operations S _i and S _j are dependent on S _k ,

It is expressed as

As described above, various dependencies exist between operations, and are written as XML documents according to the dependencies between operations and included in the agent-based P2P-MPI middleware of the present invention. That is, if there is a graph according to the dependency relationship as shown in FIG. 12, this is expressed in the form of XML code as shown in FIG. 13 and applied to the agent-based P2P-MPI middleware as a dependency description library (S38). Thereafter, according to the description of the dependency relationship as described above to generate an agent-based autonomous P2P-MPI operation module to apply it to the MPI (S40).

As described above, each resource provider that implements agent-based P2P-MPI middleware having an XML code of dependency relationship dynamically starts an operation by forming an operation group as shown in FIG. Before the group is formed, the number of duplicate operations is determined according to the availability of each resource provider, and then the group is formed.

As a result, as shown in FIG. 3, after calculating the calculation availability ratio and the calculation persistence (S30), the classification is based on the performance (S32), and then the overlay network is configured (S34). And dependence technique (S38) is applied to generate a library for grouping. The generated libraries are put into the agent-based P2P-MPI middleware of the present invention as a library.

15 is a diagram illustrating an internal configuration block of agent-based P2P-MPI middleware according to the present invention.

Agent-based P2P-MPI middleware is a middleware installed in each resource provider (including coordinator), and agent-based autonomous P2P-MPI operation module 151, agent library 152, MPI library 153, and P2P communication library. Has a structure with 154.

The P2P communication library 154 has a library that supports P2P communication between resource providers, and this P2P communication library is a P2P communication library known in the art.

The MPI library 153 is a message passing interface (MPI) library in a P2P based distributed system, and such MPI library uses a conventionally known MPI library.

Agent library 152 is located in the library formed through the process of Figure 3 according to the present invention. That is, the library S30 for calculating the calculation availability ratio and the computation persistence ratio described above, the libraries S32 and S34 used for constructing the overlay network by assigning identifiers, and the operation duplication technique and the dependency technique for applying. The libraries S36 and S38 are applied and called by the agent-based autonomous P2P-MPI operation module 151 (S40).

 The agent-based autonomous P2P-MPI operation module 151 calls the MPI library 153 and the agent library 152 to perform an agent-based autonomous P2P-MPI operation. It not only ensures continuous operation by migrating autonomously, but also duplicates operation by creating duplicates autonomously according to the operation availability ratio of a specific resource provider. In addition, the agent-based autonomous P2P-MPI operation module 151 calculates the average resource provision time and the available time to the previous profile of the resource provider and ensures reliable computation performance using migration or checkpointing techniques.

To this end, the agent-based autonomous P2P-MPI operation module 151 is composed of a plurality of functions for loading the MPI library and the agent library, and the function is based on point-to-point communication, aggregate communication, blocking mode, non-blocking mode, and the number of buffers. The call function is different accordingly.

An example of these functions is briefly described in Table 1 below.

TABLE 1
Classification function Basic function MPI_INIT, MPI_FINALIZE, MPI_COMM_SIZE, MPI_COMM_RANK Point-to-point communication Blocking mode MPI_SEND, MPI_RECEIVE Non-blocking mode MPI_ISEND, MPI_IRECEIVE Assembly communication 1 buffer MPI_BCAST 1 each of transmit and receive buffer MPI_GATHER, MPI_ALLGATHER Collecting results MPI_REDUCE, MPI_ALLREDUCE

delete

The functions of each function in [Table 1] are briefly described as follows: MPI_INIT, which is an MPI environment initialization function, MPI_COMM_SIZE, which shows the number of participating processors, MPI_COMM_RANK, which returns the currently running processor number, MPI_SEND, which sends / receives a message, and MPI_RECEIVE. Finally, there is the MPI_FINALIZE function, which terminates an MPI program. The MPI library supports point-to-point communication and aggregate communication. In point-to-point communication, one resource provider communicates with other resource providers through MPI_SEND and MPI_RECEIVE in blocking mode. In nonblocking mode, communication is performed through MPI_ISEND and MPI_IRECEIVE functions. In aggregate communication, there are various functions used when there is only one buffer or when there is only one transmit buffer and one receive buffer, and when the result is reduced. The resource provider's rank is assigned by the coordinator when the job is performed, and sends a graph of the dependencies between them to all resource providers in the workgroup.

By using the functions, the agent-based autonomous P2P-MPI operation module 151 may use a bicycle method (eg, moving to an HLV area according to the resource provider's characteristics) according to the resource provider's dynamic characteristics, and the resource provider's profile. Can provide a checkpointing technique (eg, joining, withdrawing, scheduling), a scheduling technique including performing a duplicate operation or a single operation, and a result checking technique for a malicious resource provider.

In the foregoing description of the present invention, specific embodiments have been described, but various modifications may be made without departing from the scope of the present invention. Therefore, the patent scope of the present invention is not to be determined by the above-described embodiment, and the claims will be apparent not only in the claims but also in the equivalent ranges.

As described above, the present invention, by providing an infrastructure that can perform a variety of applications in the P2P-based distributed system, can support the utilization of various fields of the P2P-based distributed computing platform, advanced science and technology It can contribute to the spread of applicability, and finally to the commercialization of P2P based distributed computing. That is, compared to the conventional P2P-based distributed system in the case of P2P-based distributed system with the agent-based P2P-MPI middleware of the present invention, there is an effect that it is possible to extend the various applications as shown in FIG.

In addition, when applying the agent-based P2P-MPI middleware of the present invention to a P2P-based distributed system, it is possible to provide an internet-based distributed computing service that can be used in a variety of advanced scientific fields.

In addition, the possibility of widespread use of P2P-based distributed systems in the entire industry can be widened by overcoming the limitations of application performance, which was the limitation of using P2P-based distributed systems.

In addition, it is possible to extend the applicability of P2P-based distributed systems to a variety of dependent and demanding applications.

Claims (35)

The first library is applied by calculating the operation persistence ratio that indicates how many resources each resource provider has provided in a P2P distributed system and the operation availability ratio that indicates the probability that each resource provider will participate in the operation. Creating a process, Resource providers are categorized according to the calculated computed persistence ratio and computed availability ratio, and each resource provider is assigned a unique identification key, and a resource provider with high performance of computed persistence ratio and computed availability ratio as the coordinator as a coordinator. After the selection, the coordinator generates a second library by applying an overlay network forming method of forming a resource identification tree with other resource providers; Generating a third library by applying a duplication technique that simultaneously executes the same task job in multiple resource providers having low operation availability ratios and aggregates these operations to shorten the computation time; A process of generating a fourth library by XML-coding the operation dependency relationship such that a calculation group is formed around a coordinator dynamically according to operation dependency relationships between resource providers. Agent-based P2P-MPI middleware design method comprising a. The method of claim 1, further comprising generating an agent-based autonomous P2P-MPI module for each resource provider and coordinator to apply the generated libraries to the MPI. The method of claim 1, wherein the operation persistence ratio is calculated by 'Ξ = 1−1 / λ' when the operation persistence ratio is Ξ and the operation withdrawal rate is λ. The MTTCF of claim 1, wherein the calculation availability ratio is a calculation availability rate Λ, an average of occurrences of operation defects indicating how often the resource provider leaves the operation performed by the resource provider, MTTCF, and a time average in which the resource provider participates in the operation, MTTCR. When the design method of agent-based P2P-MPI middleware, calculated by Λ = MTTCF / (MTTCF-MTTCR). The method of claim 1, wherein the classifying the resource providers according to the computational persistence ratio and the computational availability ratio in the process of generating the second library is characterized by the higher computational availability ratio and the higher computational persistence ratio. Location in the zone, the higher the computational availability rate and the lower the computational persistence rate, the higher the location in the half-lived volunteer (HLV) region. A method of designing an agent-based P2P-MPI middleware that locates and places a lower computational availability rate and a lower computational persistence rate in the timeoff-lived volunteer area. The global location identifier (GLID) of claim 1, wherein the unique identification key in the process of generating the second library has a bit size to indicate that it is located in a global area that is a higher level among resource providers. ), A Local Location IDentifier (LLID) with a b bit size to indicate that it is located in the local area at a lower level among the providers, and an object identifier (c bit size) to indicate the unique ID of the resource provider. A method of designing agent-based P2P-MPI middleware including an OID (Object IDentifier) and an Object Classification IDentifier (OCID) having a 2-bit size to indicate a functional role of a corresponding resource provider. The agent-based P2P-MPI middleware according to claim 6, wherein the global size is ^a size having ^a number of resource providers of 2 ^{a + b} , and the size of ^a local size is ^a size having ^a number of resource providers of 1/2 ^a . Design method. 7. The agent of claim 6, wherein the object classification identifier (OCID) is a '00' bit, a resource provider object, a '01' bit, a coordinator object, and a '10' bit, an agent indicating a start node object. Design method of P2P-MPI middleware based. 7. The method of claim 6, wherein the resource provider having the highest computational availability ratio and operation persistence ratio among the resource providers in each local area is selected as the coordinator of the local area. 10. The method of claim 9, wherein the number of coordinators is 1/2 ^a . The method of claim 1, wherein the operation duplication method of generating the third library comprises: ψ _i is the predicted completion time performed at the provider i without the volatile feature, θ _t is the estimated completion time with the volatile feature at time t, and Λ _i is the computed availability rate of the provider i The number of duplicate operation providers (n) that perform the operation

Calculating by formula, Transmitting a result of the operation to other operation duplication resource providers when there is a resource provider that completes the operation among the operation duplication resource providers performing the same operation; The operation duplication resource provider receiving the operation result cancels the operation and receives another operation from the coordinator, When all operations are completed, the coordinator of the operation group transmits a work completion message to the operation duplication resource providers who are members of the group, and the operation duplication resource providers store the work completion time. Agent-based P2P-MPI middleware design method comprising a. The method of claim 1, wherein the operation dependency relationship has a 1: 1 operation dependency relationship and an n: 1 operation dependency relationship between resource providers. delete delete delete delete delete delete delete delete delete delete delete A first step of calculating a calculation persistence ratio indicating how much time each resource provider provided resources in a P2P distributed system, and a calculation availability ratio indicating a probability that each resource provider participates in the calculation; Resource providers are categorized according to the calculated computed persistence ratio and computed availability ratio, and each resource provider is assigned a unique identification key, and a resource provider with high performance of computed persistence ratio and computed availability ratio as the coordinator as a coordinator. After the selection, the coordinator forms a resource identification tree with other resource providers to form an overlay network; A third step of applying an operation duplication method of simultaneously executing the same task job in a plurality of resource providers having a low operation availability ratio and combining these operations to reduce the computation time; Fourth step of generating XML-coded operation dependency relationship so that operation group is formed around coordinator dynamically according to operation dependency relationship between resource providers P2P-based distributed computing method comprising a. 25. The distributed computing method of claim 24, further comprising a fifth step of generating a module for each resource provider and coordinator to apply each generated library to an MPI. The P2P-based distributed computing method of claim 24, wherein the computation persistence ratio is calculated by 'Ξ = 1−1 / λ' when the computation persistence ratio is Ξ and the computation withdrawal rate is λ. The MTTCF of claim 24, wherein the operation availability ratio is MTTCF, and an average of occurrences of operation defects indicating how often the resource provider leaves the operation performed by the resource provider is MTTCR. P2P-based distributed computing method calculated by Λ = MTTCF / (MTTCF-MTTCR). 25. The method of claim 24, wherein the classifying the resource providers according to the computational persistence ratio and the computational availability ratio in the second process is performed so that the higher the computational availability ratio and at the same time, the higher the computational persistence ratio is located in the Long-Lived Volunteer (LLV) region. The higher the computational availability ratio and the lower the computational persistence ratio, the higher the computational availability rate is in the half-lived volunteer (HLV) region. A P2P-based distributed computing method in which a lower computational availability ratio and a lower computational persistence ratio are located in a timeoff-lived volunteer (TLV) domain. The global location identifier (GLID) of claim 24, wherein the unique identification key in the second process has a bit size to indicate that it is located in a global area that is a higher level among the resource providers. Local location identifier (LLID) with a b-bit size to indicate that it is located in the local area at a lower level, and an object identifier (OID) with a c-bit size to indicate the unique ID of the resource provider. ), A P2P-based distributed computing method including an object classification identifier (OCID) having a 2-bit size to indicate a functional role of the corresponding resource provider. 30. The distributed computing method of claim 29, wherein the global size is ^a size having ^a number of resource providers of 2 ^{a + b} , and the local size is ^a size having ^a number of resource providers of 1/2 ^a . . 30. The P2P of claim 29, wherein the object classification identifier (OCID) is a '00' bit, a resource provider object, a '01' bit, a coordinator object, and a '10' bit, a P2P. Based distributed computing method. 30. The distributed computing method of claim 29, wherein a resource provider having the highest computational availability ratio and a computation persistence ratio among resource providers in each local area is selected as a coordinator of the local area. 33. The distributed computing method of claim 32, wherein the number of coordinators is 1/2 ^a . The method of claim 24, wherein the operation duplication method in the third process comprises: ψ _i is the predicted completion time performed at the provider i without the volatile feature, θ _t is the estimated completion time with the volatile feature at time t, and Λ _i is the computed availability rate of the provider i The number of duplicate operation providers (n) that perform the operation

Calculating by formula, Transmitting a result of the operation to other operation duplication resource providers when there is a resource provider that completes the operation among the operation duplication resource providers performing the same operation; The operation duplication resource provider receiving the operation result cancels the operation and receives another operation from the coordinator, When all operations are completed, the coordinator of the operation group transmits a work completion message to the operation duplication resource providers who are members of the group, and the operation duplication resource providers store the work completion time. P2P-based distributed computing method comprising a. 25. The distributed computing method of claim 24, wherein the operation dependency relationship has a 1: 1 operation dependency relationship and an n: 1 operation dependency relationship between resource providers.

Images