Patent Description:
With the development of computer technologies, distributed processing has emerged. Multiple processing units may be provided, and a processing task may be performed in the multiple processing units in a distributed way. However, as processing tasks get increasingly complex, a great number of processing units are needed to coordinate operations. At this point, it becomes a technical challenge regarding how to schedule multiple processing units to perform a processing task more effectively. <CIT> A1describes a method including the operations of pairing a plurality of processes such that each process has a maximum of one interaction partner, selecting half of the data located at a process, dividing the selected half of the data into a plurality of data segments, transmitting a first data segment resulting from the dividing operation from the process to the interaction partner of the process, receiving a second data segment at the process from the interaction partner, concurrently with the transferring and receiving operations, performing a computing operation on a third data segment previously received from a previous interaction partner and a fourth data segment from the data segments, and iterating over the transmitting, receiving and computing operations until all the data segments have been exchanged. <CIT> describes a simultaneous linear equations calculation method using a memory-distributed parallel processor and the memory-distributed parallel processor solves simultaneous linear equations in an LU decomposition method in block units using an outer product. According to the method and the processor, data of column vector blocks is rearranged through a cyclic and parallel rearrangement and transfer. When an LU decomposition is performed, data to be processed in a row matrix product is divided, and the divided data is processed in a matrix calculation and simultaneously transferred for a subsequent matrix product calculation. The LU-decomposed matrix is restored to an original arrangement and then rearranged such that the matrix is divided in the row vector direction to realize a forward/backward substitution process in parallel in each processor.

With reference to the detailed descriptions below in conjunction with the accompanying drawings, the above and other features, advantages and aspects of the implementations of the present disclosure will become more apparent. In the drawings, the same or similar reference numerals represent the same or similar elements, where:.

The implementations of the present disclosure will be described in more details with reference to the drawings. Although the drawings illustrate some implementations of the present disclosure, it should be appreciated that the present disclosure can be implemented in various manners and should not be limited to the implementations explained herein. On the contrary, the implementations are provided to make the present disclosure more thorough and complete. It should be understood the drawings and implementations disclosed herein are merely for the illustration purpose.

As used herein, the term "includes" and its variants are to be read as open-ended terms that mean "includes, but is not limited to. " The term "based on" is to be read as "based at least in part on. " The term "one implementation" or "the implementation" is to be read as "at least one example implementation. " The terms "first", "second" and so on can refer to same or different objects. The following text also can include other explicit and implicit definitions.

In the context of the present disclosure, the processing task is an AllReduce task, which is used for performing accumulator operations on to-be-processed data. The processing task is performed at multiple processing units (e.g. GPU, AI-specific chips, etc.). For example, the number of multiple processing units may be denoted as n. For the sake of description, an example of performing the processing task at <NUM> processing units will be cited by way of explanation in the context of the present disclosure. It will be understood the value of n may further be a larger or smaller integer.

There have been provided varieties of technical solutions for AllReduce operations. In a ring-based AllReduce solution, to-be-processed data may be divided into n portions, and the n portions may be respectively processed at n processing units which are connected in a ring. Each processing unit transmits its accumulated result to the next processing unit and receives an accumulated result from the last processing unit in the ring.

First of all, description is presented below to an application environment of the present disclosure with reference to <FIG> schematically shows a block diagram 100A of performing a processing task by multiple processing units. As depicted, <NUM> processing units <NUM>, <NUM>, <NUM> and <NUM> connected in a ring are used to perform the processing task. Here to-be-processed data is assumed as M. Data M may be divided into <NUM> portions, as such each data portion is M/<NUM>. Respective to-be-processed M/<NUM> of the to-be-processed data is sent to each processing unit.

Data of each processing unit is evenly divided into <NUM> portions, and the ith processing unit copies the ith data to a subsequent processing unit. Each processing unit accumulates data received from the previous processing unit with local corresponding data and copies an accumulated result to the subsequent processing unit. In the next round, each processing unit waits for an accumulated result from the previous processing unit, accumulates the received accumulated result with local corresponding data and copies a new accumulated result to the subsequent processing unit. The above steps are repeated, until each processing unit has its own portion of complete accumulated result. Subsequently, each processing unit copies its own portion of complete accumulated result to the subsequent processing unit, and the subsequent processing unit then copies this portion of complete accumulated result to a further subsequent processing unit after receiving it, until each processing unit has the entire complete accumulated result.

<FIG> schematically shows a block diagram of a processing result after multiple processing units perform the processing task. After performing the above described AllReduce task, each of the processing units <NUM>, <NUM>, <NUM> and <NUM> has the entire complete accumulated result. In order to control n processing units to coordinate in the above described procedure, enormous communication resources are needed to schedule data accumulating, copying and receiving, so the scalability is rather poor.

There is further provided a bidirectional ring-based AllReduce solution, in which multiple processing units are divided into horizontal and vertical rings. However, steps of the solution require larger communication overheads, so the solution can hardly be applied in massive data processing. Therefore, it is desirable to provide a more effective approach to implement AllReduce processing tasks.

In order to at least partly solve the drawbacks in the above technical solutions, according to example implementations of the present disclosure, there is provided a technical solution for performing a processing task. Specifically, example implementations of the present disclosure propose the concept of operation queue, and at a processing unit, corresponding operation queues are built for different types of operations. Subsequently, operations in various operation queues are performed at the processing unit respectively based on a dependency relationship between multiple operations that are to be performed at the processing unit and multiple operations that are to be performed at other processing units, so as to accomplish a portion of the processing task which is allocated to the processing unit. A brief description is presented below to the procedure of the present disclosure with reference to <FIG>.

<FIG> schematically shows a block diagram <NUM> for performing a processing task according to example implementations of the present disclosure. For the sake of description, <FIG> merely illustrates the processing performed at two of multiple processing units. When a group of processing units include n processing units, a processing task <NUM> may be divided into n portions. As shown in <FIG>, the processing task <NUM> includes multiple portions <NUM>, <NUM>, etc., and one portion of the processing task <NUM> is processed by one processing unit. For example, the portion <NUM> may be processed by the processing unit <NUM>, the portion <NUM> may be processed by the processing unit <NUM>. For the sake of description, the processing unit <NUM> processing the portion <NUM> is taken by way of example below, and the processing unit <NUM> processing the portion <NUM> involves a similar procedure.

Here each portion includes operations of a first type and operations of a second type. The portion <NUM> includes operations of a first type <NUM> and operations of a second type <NUM>. At the processing unit <NUM>, a first queue <NUM> for performing operations of the first type <NUM> and a second queue <NUM> for performing operations of the second type <NUM> is built. Depending on the type of the operations, here the operations may be sorted in an order of execution in a corresponding queue.

Subsequently, based on a definition of the processing task <NUM>, a dependency relationship <NUM> between a group of operations that are to be performed at the processing unit <NUM> and a group of operations that are to be performed at other processing unit <NUM> in the multiple processing units is obtained. The dependency relationship here refers to an order for performing the operations. For example, regarding operations to be performed at the processing unit <NUM>, a copy operation of copying a data block to a subsequent processing unit may not depend on any other operations, but an accumulation operation depends on a previous processing unit already copying a data block to the processing unit <NUM>. Having obtained the dependency relationship <NUM>, operations in the first queue <NUM> and operations in the second queue <NUM> are performed respectively at the processing unit <NUM> based on the dependency relationship <NUM>.

Similarly, for the processing unit <NUM>, the portion <NUM> allocated to the processing unit <NUM> includes operations of a first type <NUM> and operations of a second type <NUM>, and a first queue <NUM> and a second queue <NUM> is built respectively so as to manage various types of operations. Subsequently, operations in the first queue <NUM> and operations in the second queue <NUM> are performed respectively based on the dependency relationship <NUM>. With the technical solution of the present disclosure, by scheduling the execution of different types of operations based on queues and the dependency relationship, the AllReduce parallelism may be significantly increased, and various time and resource overheads during execution may be reduced. Further, the technical solution of the present disclosure may be combined with existing AllReduce methods.

With reference to <FIG>, description is presented below to more details about example implementations of the present disclosure. <FIG> schematically shows a flowchart of a method <NUM> for performing a processing task according to example implementations of the present disclosure. Here, the portion <NUM> of the processing task <NUM> will be performed at the processing unit <NUM>. At block <NUM>, a first queue for performing operations of a first type and a second queue for performing operations of a second type are built at a processing unit.

The processing task <NUM> is an AllReduce task. According to example implementations of the present disclosure, multiple processing units are connected in a ring. For example, the multiple processing units <NUM>, <NUM>, <NUM> and <NUM> may be connected successively in a ring as shown in <FIG>. For another example, the multiple processing units may be divided into horizontal and vertical directions and multiple processing units are connected in each of rings in the two directions.

It will be understood to-be-processed data which is to be processed by the processing task <NUM> may be divided into multiple data blocks. Suppose the processing task <NUM> is to be performed by n processing units, then the to-be-processed data may be divided into n data blocks, and a corresponding data block may be sent to each processing unit. In this case, each processing unit may receive one data block, and this data block is a portion of the to-be-processed data of the processing task <NUM>, which is to be processed at the processing unit.

For the sake of description, the entire to-be-processed data is assumed as M. In a case where <NUM> processing units are used, the to-be-processed data may be divided into <NUM> data blocks. In this case, to-be-processed data blocks may be sent to the processing units <NUM>, <NUM>, <NUM> and <NUM> respectively. At each processing unit, received data may be divided into <NUM> portions. In this case, the divided data may include data A1, B1, C1 and D1 at the processing unit <NUM>; the divided data may include data A2, B2, C2 and D2 at the processing unit <NUM>, and so on and so forth. Description is presented below to an example of operations at each processing unit. <FIG> schematically shows a block diagram <NUM> of data distribution among the multiple processing units according to example implementations of the present disclosure. For example, Table <NUM> below shows an example of operations performed at the processing unit <NUM>, and when performing the operations, the processing unit <NUM> already has the data A2, B2, C2 and D2.

As shown in Table <NUM>, the first column lists identifiers of operations, the second column lists types of operations, and the third column lists contents of operations. Table <NUM> merely illustrates a part of operations to be performed at the processing unit <NUM>, and after operation <NUM>, accumulation operations and copy operations may be performed alternatively until an accumulated result (A1+A2+A3+A4) is obtained. It will be understood the accumulated result (A1+A2+A3+A4) here is merely a partial complete accumulated result. Thus, each processing unit needs to copy its local partial complete accumulated result to the next processing unit, and then the next processing unit performs copy circularly, until each processing unit has the entire complete accumulated result.

The group of operations to be performed at the processing unit <NUM> may include copy operations and accumulation operations. In this case, a first queue and a second queue is built respectively based on types of operations to be performed at the processing unit <NUM>. Specifically, the first queue may include accumulation operations as shown in Table <NUM> below, and the second queue may include copy operations as shown in Table <NUM> below.

More details about copy operations and accumulation will be described with reference to <FIG> and <FIG>. It will be understood the copy operation here may copy an accumulated result/data block at a processing unit to a subsequent processing unit which is connected to and arranged after the processing unit. For the processing unit <NUM>, as shown by an arrow <NUM>, the processing unit <NUM> may copy data A1 to the processing unit <NUM> to form a duplicate. For the processing unit <NUM>, as shown by an arrow <NUM>, the processing unit <NUM> may copy data B2 to the processing unit <NUM> to form a duplicate. Similar copy operations may be performed at other processing units. Though not shown in <FIG>, the object of the copy operation may further be an accumulated result at a processing unit.

According to example implementations of the present disclosure, an accumulation operation refers to accumulating a data block at a processing unit and an accumulated result which is copied to the processing unit from a previous processing unit connected to and arranged before the processing unit, to form an accumulated result of the processing unit. <FIG> schematically shows a block diagram <NUM> for performing accumulation operations at multiple processing units according to example implementations of the present disclosure. <FIG> shows the state of the processing unit <NUM> after the copy operations in <FIG>, and after the copy operations, the processing unit <NUM> already has the duplicate of data A1. At the processing unit <NUM>, an accumulated result <NUM> (i.e. A1+A2) may be determined based on data A2 and the duplicated of data A1. Similarly, accumulated results of other data may further be determined at other processing units.

According to example implementations of the present disclosure, in order to perform copy operations and accumulation operations, code for executing a corresponding type of operation is loaded to a processing unit. <FIG> schematically shows a block diagram <NUM> for loading code to a processing unit according to example implementations of the present disclosure. As depicted, a host <NUM> may be connected to the processing units <NUM>, <NUM>, <NUM> and <NUM>. Here the host <NUM> loads first code for performing operations of accumulation type and second code for performing operations of copy type to memories of various processing units.

It will be understood the procedure of loading code to each processing unit is quite similar. For the sake of simplicity, description is presented below to only the loading procedure for the processing unit <NUM>. According to example implementations of the present disclosure, first code <NUM> for performing accumulation operations and second code <NUM> for performing copy operations is respectively loaded to a memory <NUM> of the processing unit <NUM>.

After the first code <NUM> and the second code <NUM> are loaded to the memory <NUM>, the processing unit <NUM> may perform operations corresponding to the code rapidly. According to example implementations of the present disclosure, in order to increase the response speed of the processing unit <NUM>, at least one of the first code <NUM> and the second code <NUM> may be retained in the memory <NUM> of the processing unit <NUM>. With example implementations of the present disclosure, code for data copy and data accumulation is preloaded to various processing units and resides in memories of various processing units, so that extra time and resource overheads caused by repetitive loading/releasing may be avoided.

In this case, operations in the first queue are performed based on the first code <NUM>, and operations in the second queue are performed based on the second code <NUM>. It will be understood since copy operations take bandwidth resources between processing units, and accumulation operations take computing resources in the processing units, regarding some operations without a dependency relationship, operations in the two queues are performed in parallel.

At block <NUM>, a dependency relationship between multiple operations may be determined according to a definition of the processing task <NUM>. A dependency relationship between a group of operations that are to be performed at the processing unit <NUM> and a group of operations that are to be performed at other processing units in the multiple processing units is obtained. Description on how to obtain the dependency relationship is presented below by taking multiple operations to be performed at the processing unit <NUM> as an example. Continuing the above example, it is assumed that <NUM> data blocks are already transmitted to the processing units <NUM>, <NUM>, <NUM> and <NUM>. It may be determined from the AllReduce procedure that the dependency relationship between operations is as shown in the last column of Table <NUM>.

Returning to <FIG>, at block <NUM>, operations in the first queue and operations in the second queue are performed respectively based on the dependency relationship. It will be understood that a hardware interrupt may be used to notify a processing unit that the dependency relationship for performing a certain specific operation is satisfied, and further the processing unit may be triggered to perform the specific operation. According to example implementations of the present disclosure, if it is determined that an operation in either of the first queue and the second queue is completed at a processing unit, and then a hardware interrupt of the processing unit is used to notify other processing units.

With example implementations of the present disclosure, tasks in a queue are scheduled based on a hardware interrupt of a processing unit, so that the processing unit itself guarantees the sequence for performing tasks, and unnecessary communication with the host is avoided. With the technical solution of the present disclosure, the AllReduce parallel efficiency may be increased significantly, and various time and resource overheads during execution may be reduced. Hereinafter, how to make a notification based on a hardware interrupt will be described with reference to <FIG> and <FIG> respectively.

<FIG> schematically shows a block diagram <NUM> of triggering a hardware interrupt after completion of operations in a copy queue according to example implementations of the present disclosure. <FIG> shows a copy queue <NUM> for the processing unit <NUM>. The copy queue <NUM> may include multiple copy operations. For example, a copy operation <NUM> in the copy queue <NUM> represents operation <NUM> in Table <NUM>, i.e. copying data B2 at the processing unit <NUM> to the subsequent processing unit <NUM>. As seen from the dependency relationship in Table <NUM>, since this operation does not depend on other operations, it may be performed directly.

Further, based on the dependency relationship, the accumulation operation at the subsequent processing unit <NUM> depends on the copy operation <NUM>. Thus, after completing the copy operation <NUM>, a hardware interrupt <NUM> may be generated so as to notify <NUM> the subsequent processing unit <NUM> to perform a corresponding accumulation operation. At the subsequent processing unit <NUM>, once the hardware interrupt <NUM> is received from the previous processing unit <NUM>, an accumulation operation may be performed (i.e. received data B2 being accumulated with own data block B3).

According to example implementations of the present disclosure, a processing unit and a subsequent processing unit share a cache area, so an accumulated result may be copied from the processing unit to the cache area so as to realize a copy operation. For example, the processing unit <NUM> and the processing unit <NUM> may share a cache area, and in such case, the processing unit <NUM> may copy data to the cache area and the processing unit <NUM> may read data from the cache area. It will be understood although <FIG> only describes the example of generating the hardware interrupt <NUM> after performing one copy operation <NUM> in the copy queue <NUM>, a subsequent processing unit may be notified in a similar way to perform a corresponding accumulation operation after other copy operations are performed.

According to example implementations of the present disclosure, if an accumulation operation in the first queue has been performed at a processing unit, based on the hardware interrupt, a previous processing unit may be notified to perform a next copy operation in the second queue. A detailed description is presented below with reference to <FIG>, which schematically shows a block diagram <NUM> of triggering a hardware interrupt after completing operations in an accumulation queue according to example implementations of the present disclosure. <FIG> shows an accumulation queue <NUM> for the processing unit <NUM>, the accumulation queue <NUM> including multiple copy operations. An accumulation operation <NUM> in the accumulation queue <NUM> as shown in <FIG> represents operation <NUM> in Table <NUM>, i.e. data A1 received from the processing unit <NUM> is accumulated with local data A2 so as to obtain an accumulated result (A1+A2). Since this operation depends on the previous processing unit <NUM> copying data A1 to the processing unit <NUM>, the accumulation operation <NUM> may be initiated after the processing unit <NUM> receives the hardware interrupt from the processing unit <NUM>.

Further, based on the dependency relationship of the accumulation operation <NUM>, the copy operation of the previous processing unit <NUM> copying a subsequent accumulated result to the processing unit <NUM> will depend on the accumulation operation <NUM>. Therefore, after completing the accumulation operation <NUM>, a hardware interrupt <NUM> may be generated so as to notify <NUM> the previous processing unit <NUM> to copy the subsequent accumulation result to the processing unit <NUM>. At the previous processing unit <NUM>, once the hardware interrupt <NUM> is received from the processing unit <NUM>, the processing unit <NUM> may perform a copy operation.

With example implementations of the present disclosure, since copy operations and accumulation operations use bandwidth resources and computing resources respectively, copy operations and accumulation operations to be performed are stored using a copy queue and an accumulation queue respectively. The two types of operations do not cause a resource conflict by using the copy queue and the accumulation queue, so the possibility of parallel execution may be increased. Further, as compared with technical solutions in which the host schedules the running of processing units or polling technology is used to constantly confirm whether the dependency relationship is satisfied, using a hardware interrupt to make a notification that the dependency relationship is satisfied may greatly improve the efficiency of scheduling operations and further improve the execution efficiency of a group of operations.

According to example implementations of the present disclosure, if it is determined all operations in the first queue and the second queue have been performed at the processing unit, then a message may be sent to indicate that the processing unit has processed a portion of the processing task. It will be understood although in example implementations of the present disclosure, the specific procedure of performing the processing task has been described in the context of only one processing unit, operations which are performed at other processing units among the multiple processing units are also similar. By performing the above method <NUM> at all of the multiple processing units in parallel, the efficiency that each processing unit performs the portion of processing task allocated to itself may be improved, so that the execution efficiency of the entire processing task may be improved.

Implementations of the method <NUM> for performing a processing task have been described in detail. According to example implementations of the present disclosure, there is further provided a device for performing a processing task. A detailed description is presented below with reference to <FIG>, which schematically shows a block diagram of an apparatus <NUM> for performing a processing task according to example implementations of the present disclosure. One of a plurality of portions of the processing task includes a group of operations that are to be performed at one of a plurality of processing units, the group of operations including operations of a first type and operations of a second type. As shown in <FIG>, the apparatus <NUM> includes: a building module <NUM> configured to build a first queue for performing operations of the first type and a second queue for performing operations of the second type; an obtaining module <NUM> configured to obtain, according to a definition of the processing task, a dependency relationship between a group of operations that are to be performed at the processing unit and a group of operations that are to be performed at other processing units among the plurality of processing units; and a performing module <NUM> configured to perform operations in the first queue and operations in the second queue respectively based on the dependency relationship.

According to example implementations of the present disclosure, the device further includes: a loading module configured to load to the processing unit first code for performing a first group of operations of the first type and second code for performing a second group of operations of the second type.

According to example implementations of the present disclosure, the performing module <NUM> includes: a first performing module configured to perform operations in the first queue based on the first code; and a second performing module configured to perform operations in the second queue based on the second code.

According to example implementations of the present disclosure, the device further includes: a retaining module configured to retain at least one of the first code and the second code in a memory of the processing unit.

According to example implementations of the present disclosure, the device further includes: a receiving module configured to receive, at the processing unit, a data block, which is to be processed at the processing unit, in to-be-processed data of the processing task, the data block resulting from dividing the to-be-processed data by the number of the plurality of processing units.

According to example implementations of the present disclosure, the performing module <NUM> further includes: a data processing module configured to perform, at the processing unit, operations in the first queue and operations in the second queue on the data block.

According to example implementations of the present disclosure, the processing task is an AllReduce task, and the plurality of processing units are connected in a ring.

According to example implementations of the present disclosure, the first group of operations include an accumulation operation for accumulating a data block at the processing unit to an accumulated result which is copied to the processing unit from a previous processing unit connected to and arranged before the processing unit, to form an accumulated result of the processing unit.

According to example implementations of the present disclosure, the second group of operations include a copy operation for copying an accumulated result at the processing unit to a subsequent processing unit connected to and arranged after the processing unit.

According to example implementations of the present disclosure, the performing module <NUM> includes: a notifying module configured to use a hardware interrupt of the processing unit to notify other processing units in response to completing an operation in any of the first queue and the second queue at the processing unit.

According to example implementations of the present disclosure, the notifying module includes: a first notifying module configured to notify the previous processing unit based on a hardware interrupt to perform a next copy operation in the second queue in response to completing an accumulation operation in the first queue at the processing unit.

According to example implementations of the present disclosure, the notifying module includes: a second notifying module configured to notify the subsequent processing unit based on the hardware interrupt to perform a next accumulation operation in the first queue in response to completing a copy operation in the second queue at the processing unit.

According to example implementations of the present disclosure, the processing unit and the subsequent processing unit share a cache area, and the device further includes: a copying module configured to copy at least one of the data block and the accumulated result from the processing unit to the cache area.

According to example implementations of the present disclosure, the device further includes: a reporting module configured to report that the processing unit has performed the portion of the processing task in response to determining that all operations in the first queue and the second queue have been performed at the processing unit.

<FIG> shows a block diagram of a computing device <NUM> which is applicable to implement multiple implementations of the present disclosure. The device <NUM> may be used to implement the method described with reference to <FIG>. As depicted, the device <NUM> includes a central process unit (CPU) <NUM>, which can execute various suitable actions and processing based on the computer program instructions stored in the read-only memory (ROM) <NUM> or computer program instructions loaded in the random-access memory (RAM) <NUM> from a storage unit <NUM>. The RAM <NUM> can also store all kinds of programs and data required by the operations of the device <NUM>. CPU <NUM>, ROM <NUM> and RAM <NUM> are connected to each other via a bus <NUM>. The input/output (I/O) interface <NUM> is also connected to the bus <NUM>.

A plurality of components in the device <NUM> is connected to the I/O interface <NUM>, including: an input unit <NUM>, such as keyboard, mouse and the like; an output unit <NUM>, e.g., various kinds of display and loudspeakers etc.; a storage unit <NUM>, such as magnetic disk and optical disk etc.; and a communication unit <NUM>, such as network card, modem, wireless transceiver and the like. The communication unit <NUM> allows the device <NUM> to exchange information/data with other devices via the computer network, such as Internet, and/or various telecommunication networks.

The above described methods and processes, such as the method <NUM> are executed by the processing unit <NUM>. For example, in some implementations, the method <NUM> can be implemented as a computer software program tangibly included in the machine-readable medium, e.g., the storage unit <NUM>. In some implementations, the computer program can be partially or fully loaded and/or mounted to the device <NUM> via ROM <NUM> and/or the communication unit <NUM>. When the computer program is loaded to the RAM <NUM> and executed by the CPU <NUM>, one or more steps of the above described method <NUM> can be implemented. Alternatively, in other implementations, the CPU <NUM> may be configured in other suitable manners (for example, using a firmware) to perform the method <NUM>.

According to example implementations of the present disclosure, there is provided a computer readable storage medium having a computer program stored thereon. The program, when executed by a processor, implements the method described in the present disclosure.

The functionally described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-Programmable Gate Arrays (FPGAs), Application-specific Integrated Circuits (ASICs), Application-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), and the like.

Program code for carrying out methods of the subject matter described herein may be written in any combination of one or more programming languages. The program code may be executed entirely on a machine, partly executed on the machine, or used as a stand-alone software package to be partly executed on the machine and partly executed on a remote machine, or to be entirely executed on the remote machine or server.

In the context of the subject matter described herein, a machine readable medium may be any tangible medium that may contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. The machine readable medium may be a machine readable signal medium or a machine readable storage medium. A machine readable medium may include but not limited to an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples of the machine readable storage medium would include an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing.

Likewise, while several specific implementation details are contained in the above discussions, these should not be construed as limitations on the scope of the subject matter described herein. Certain features that are described in the context of separate implementations may also be implemented in combination in a single implementation. Conversely, various features that are described in the context of a single implementation may also be implemented in multiple implementations separately or in any suitable sub-combination.

Claim 1:
A method for performing an AllReduce processing task by a plurality of processing units,
wherein the processing task is divided into a plurality of portions, each portion being processed by a processing unit of the plurality of processing units,
each portion comprising a group of operations that are to be performed at a processing unit of the plurality of processing units, the group of operations comprising operations of a first type and operations of a second type, the method comprising:
building, at each processing unit, a first queue for performing the operations of the first type and a second queue for performing the operations of the second type;
obtaining a dependency relationship between a group of operations that are to be performed at a processing unit of the plurality of processing units and a group of operations that are to be performed at other processing units among the plurality of processing units; and
performing operations in the first queue and operations in the second queue respectively at a processing unit based on the dependency relationship;
loading, to a memory of the processing unit, a first code for performing a first group of operations of the first type and a second code for performing a second group of operations of the second type;
wherein performing operations in the first queue and operations in the second queue respectively at the processing unit based on the dependency relationship comprises:
performing the operations in the first queue based on first code; and
performing the operations in the second queue based on second code;
wherein the operations in the first queue and the operations in the second queue are performed in parallel.