METHOD AND APPARATUS WITH PROCESS SCHEDULING

A method and apparatus with process scheduling is provided. The method includes receiving operation requests from a plurality of processes; determining priority information of a plurality of near memory processors based on predetermined state information of a plurality of memories which correspond to the plurality of near memory processors; allocating the received operation requests to at least one near memory processor based on the determined priority information; and updating state information of at least one memory of the plurality of memories corresponding to the at least one near memory processor in a state table.

CROSS-REFERENCE TO RELATED APPLICATION

BACKGROUND

The following description relates to a method and apparatus with process scheduling.

2. Description of Related Art

Recently, interest in artificial intelligence has increased in various diverse industries including financial and medical industries as well as information technology (IT) industries. Deep learning, which is a field of artificial intelligence, may refer to technology that learns a deep neural network in which a number of layers of an existing neural network is increased and may use the deep neural network for user recommendation, pattern recognition, or inference, for example.

SUMMARY

In a general aspect, a processor-implemented process scheduling method includes receiving operation requests from a plurality of processes; determining priority information of a plurality of near memory processors based on predetermined state information of a plurality of memories which correspond to the plurality of near memory processors; allocating the received operation requests to at least one near memory processor of the plurality of near memory processors based on the determined priority information; and updating state information of at least one memory of the plurality of memories corresponding to the at least one near memory processor in a state table.

The plurality of memories may include at least one of a memory rank, a memory bank, a dual in-line memory module (DIMM), and a single in-line memory module (SIMM).

The state information comprises state information regarding the plurality of near memory processors which respectively correspond to each of the plurality of memories.

The state information may include at least one of priority information, write state information, read state information, operation size information, required operation time information, operation target data identification information, memory temperature information, and/or channel information.

The priority information may include information that is determined based on at least one of the write state information, the read state information, the required operation time information, the operation size information, the memory temperature information, and/or the channel information.

The priority information may include information that is determined by assigning a weight to the write state information and the read state information.

The allocating of the operation requests to the at least one near memory processor comprises allocating the operation requests to a near memory processor. of the plurality of near memory processors configured to end first an operation request currently being processed based on required operation time information, when all near memory processors are performing an operation.

The allocating of the received operation requests to the at least one near memory processor comprises allocating the received operation requests to a near memory processor, based on channel information of each of at least two near memory processors, when the at least two near memory processors have a same priority based on priority information of the at least two memory processors.

The allocating of the received operation requests to the at least one near memory processor may include determining a near memory processor among the plurality of near memory processors to process the received operation requests based on write information and read information of the plurality of near memory processors; and allocating the received operation requests to the determined near memory processor.

The plurality of processes may include processes to which a plurality of batches divided from a received job request is respectively allocated.

The batch may be configured to have a size that is determined based on size information of the received job request and resource information of the at least one memory.

The method may include by a near memory processor, of the at least one near memory processor, to which the operation request is allocated, performing a write operation and a read operation in a memory of the plurality of memories corresponding to the near memory processor.

The performing of the write operation and the performing of the read operation comprise, by the near memory processor, performing a write operation of a second process that is a succeeding process before a last read operation of a first process that is a preceding process.

The method may include storing an operation request of the received operation requests in a scheduler, comprising at least a memory, when a size of the operation request is less than a predetermined size.

The allocating of the received operation requests to the at least one near memory processor based on the determined priority information may include allocating at least one operation request of the process to at least one near memory processor when a number of the plurality of near memory processors is greater than a number of the plurality of processes.

In a general aspect, an apparatus includes a processor configured to: receive operation requests from a plurality of processes; determine priority information of a plurality of near memory processors based on predetermined state information of a plurality of memories which correspond to the plurality of near memory processors; allocate the received operation requests to at least one near memory processor based on the determined priority information; and update state information of at least one memory of the plurality of memories corresponding to the at least one near memory processor in a state table.

The apparatus may be an electronic device.

In a general aspect, an apparatus includes a scheduler including at least a memory; and one or more processors configured to: divide a job request into a plurality of batches corresponding to a plurality of processes and allocate the plurality of processes to a plurality of near memory processors based on a state table of the scheduler, wherein the allocating the plurality of processes to the plurality of near memory processors comprises: receiving state information of each of the plurality of near memory processors from the scheduler; and determining a near memory processor to which an operation request of one of the plurality of processes is to be allocated based on write state information and read state information of the plurality of near memory processors.

The determined near memory processor may be configured to perform a write operation of a second process that is a succeeding process before a last read operation of a first process that is a preceding process.

The read operation and the write operation may be performed simultaneously.

Throughout the drawings and the detailed description, unless otherwise described or provided, the same drawing reference numerals will be understood to refer to the same or like elements, features, and structures. The drawings may not be to scale, and the relative size, proportions, and depiction of elements in the drawings may be exaggerated for clarity, illustration, and convenience.

DETAILED DESCRIPTION

The terminology used herein is for the purpose of describing particular examples only, and is not to be used to limit the disclosure. As used herein, the singular forms “a,” “an,” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. As used herein, the term “and/or” includes any one and any combination of any two or more of the associated listed items. As used herein, the terms “include,” “comprise,” and “have” specify the presence of stated features, numbers, operations, elements, components, and/or combinations thereof, but do not preclude the presence or addition of one or more other features, numbers, operations, elements, components, and/or combinations thereof.

In addition, terms such as first, second, A, B, (a), (b), and the like may be used herein to describe components. Each of these terminologies is not used to define an essence, order, or sequence of a corresponding component but used merely to distinguish the corresponding component from other component(s).

In an example, a processor, e.g., one or more processors, of an electronic device may execute, for example, instructions (e.g., coding) and may control at least one another component (e.g., hardware component or software component) of the electronic device, and may perform various data processing or other operations as non-limiting examples. In an example, as at least a portion of data processing or other operations, the processor may store an instruction or data received from another component in a volatile memory, may process the instruction or the data stored in the volatile memory, and may store result data in a nonvolatile memory. In an example, the processor may include a main processor (e.g., a central processing device and an application processor) or an auxiliary processor (e.g., a graphical processing device, a neural processing unit (NPU), an image signal processor, a sensor hub processor, and a communication processor) operable independently from or together with the main processor. For example, when the electronic device includes the main processor and the auxiliary processor, the auxiliary processor may be set to use less power than that of the main processor or to specialize in a specified function. The auxiliary processor may be implemented separate from or as a portion of the main processor. Herein, it is noted that use of the term ‘may’ with respect to an example or embodiment, e.g., as to what an example or embodiment may include or implement, means that at least one example or embodiment exists where such a feature is included or implemented while all examples and embodiments are not limited thereto.

FIG.1illustrates an example method of scheduling a plurality of processes, in accordance with one or more embodiments.

FIG.1illustrates a job request110, a plurality of batches111,112,113,114,115, and116, a plurality of processes121,122,123,124,125, and126, a scheduler130, a plurality of memories140,150,160, and170, and a plurality of near memory processors141,151,161, and171respectively corresponding to the plurality of memories140,150,160, and170.

In an example, a processor may receive an operation request from each of the plurality of processes121,122,123,124,125, and126. In an example, the process used herein may refer to instructions that are continuously, or over a period of time, executed in a computer. In another example, a process may refer to a unit of a job to which a system resource is allocated from an operating system (OS). The process may include at least one thread. In an example, the thread may refer to a unit of several flows that are executed in the process. The thread is a flow of several executions that operate in a single process and may be executed while sharing an address space or resources in the process between threads in the same process. In an example, a separate stack may be allocated to each thread in the process, and code data and a heap area may be shared.

In an example, a plurality of processes may include processes to which a plurality of batches divided from the job request110is respectively allocated. As a non-limited example, the job request110used herein may refer to a program, e.g., written by a user to run on a computer and input data used to execute the program. The processor may divide the job request110into the plurality of batches, and simultaneously process the same. That is, the processor may perform a multi-process operation of dividing a single job request110into the plurality of batches, allocating the plurality of batches to the plurality of processes, and then performing simultaneous processing.

In an example, a plurality of batches may have different sizes. In an example, embedding lookup operation requests transmitted from the processes121,122,123,124,125, and126to the near memory processors141,151,161, and171may have different computation amounts (e.g., a number of indices in a lookup table). That is, since the number of indices in the lookup table that is a target of embedding lookup operation may all be different, a size of a batch may need to be changed.

In an example, a batch may include a batch having a size that is determined based on size information of the job request110and resource information of a memory. In an example, a size of data that may be stored in a memory may be limited. Since the size of data may be limited, a size of a batch may need to be determined based on resource information of the memory. Therefore, the processor may determine the size of the batch that may be stored in the memory based on the resource information of the memory. Additionally, the processor may also determine the size of the batch that may be processed by a near memory processor based on the resource information of the memory. Accordingly, the processor may perform errorless processing on the job request110through a multi-process manner by determining the size of the batch that does not exceed the limit of the memory.

In an example, an operation request may include a deep learning operation request. The deep learning operation request may include an operation request necessary for the learning of a deep learning model or inference implementing the deep learning model. The deep learning operation request may include, for example, an embedding lookup operation request. Embedding lookup may refer to searching for and computing an index selected from a lookup table in which large-sized list-format data is stored. In an example, embedding lookup operation may refer to, when the processor selects indices 1, 3, 6, 8, and 10, finding embedding vectors corresponding to the indices 1, 3, 6, 8, and 10 from the lookup table and then performing the operation thereof. The near memory processor1151may concatenate the embedding vectors corresponding to the indices 1, 3, 6, 8, and 10. In another example, the near memory processor1151may sum up the embedding vectors corresponding to the indices 1, 3, 6, 8, and 10. The aforementioned deep learning operation request is provided as an example only and the examples are not limited thereto.

In an example, the processor may allocate operation requests to at least one near memory processor based on priority information. In another example, the processor may allocate an operation request to a near memory processor based on priority information among the plurality of near memory processors141,151,161, and171using the scheduler130that includes a memory state table. The memory state table is further described below with reference toFIG.2.

In an example, the scheduler130may include a processing circuitry configured to determine to which near memory processor operation requests received from the plurality of processes121,122,123,124,125, and126are to be allocated to perform an operation. The scheduler130may include the memory state table. In an example, the memory state table may refer to a table that stores state information of a near memory processor corresponding to each memory. The processor may determine a near memory processor to process an operation request by implementing the scheduler130that includes the memory state table.

In an example, a memory may refer to a set that includes at least one memory chip. The memory may include at least one of a memory rank, a memory bank, a dual in-line memory module (DIMM), and a single in-line memory module (SIMM). In an example, the memory rank may refer to a single block or area generated using a portion or all of a memory chip in a single memory module. In an example, a single rank may refer to a data block of a 64-bit range. If a single chip=8 bit, the single rank may include eight chips. If a single chip=4 bit, the single rank may include 16 chips. A plurality of ranks may be present in a single DIMM. In an example, the memory bank may refer to a memory slot. The memory bank may refer to a set of memory chips connected to the same control line to be simultaneously accessible. In an example, the DIMM may refer to a memory module in which a plurality of DRAM chips is mounted on a circuit board and may be used as a main memory of a computer. The DIMM may include a plurality of ranks.

In an example, priority information may include information about suitability of each near memory processor in processing a current operation request. In an example, the priority information, as priority information about each of the plurality of near memory processors141,151,161, and171, may include information regarding how suitable a corresponding near memory processor is for processing an operation request. The priority information may include priority score of each of the plurality of near memory processors141,151,161, and171. A near memory processor with higher priority score is more likely to process the operation request. A method of determining, by the processor, a near memory processor to process an operation request based on priority information is further described below with reference toFIG.2.

Deep learning may be beneficial in improving the performance of processors that perform an operation.

In one or more embodiments, the data communication amount between a memory and a processor are improved, in an example in which a memory and a processor are separated.

In an example, the processor may allocate the operation request to the determined near memory processor and may update state information of at least one memory corresponding to at least one near memory processor in a state table (e.g., a state table200ofFIG.2A). In an example, the processor may allocate the operation request to the near memory processor1151corresponding to the memory1150. The near memory processor1151may correspond to a near memory processor with highest priority score. The processor may determine that the near memory processor1151processes the operation request implementing the scheduler130. The processor may allocate the operation request to the near memory processor1151and may update state information about the near memory processor1151. The processor may change write state information of the near memory processor1151from an idle state to a busy state. In another example, the processor may change read state information of the near memory processor1151from an idle state to a busy state.

In an example, to increase a deep learning operation speed, only operation results may be received from a memory after performing a deep learning operation using not the processor (e.g., a CPU and an MPU) but an operator (e.g., a near memory processor) connected to each memory by connecting the operator to each memory. This configuration may be referred to as near memory processing. The near memory processing may accelerate an operation speed, for example, in such a manner that a processor (e.g., a CPU) implements a near memory operator in a memory (e.g., a rank, a bank, and a DIMM). That is, the near memory processing may reduce a bandwidth by adding an operator device to each memory to prevent an increase in the bandwidth when reading or writing a large amount of data from or to a memory, or may accelerate the operation speed by decreasing latency.

However, there may be a program that operates by generating a plurality of processes (or threads). When the plurality of processes is generated and each process issues an instruction with a different size to a near memory processor present in a memory, a processing time of each near memory processor may vary. In this, a method of determining a near memory processor for each process and then performing an operation may be inefficient in terms of an overall operation time. In an example, if a computation amount performed by one instruction for a near memory processor is different, an execution time of each of the plurality of near memory processors may differ. Although operation requests are simultaneously input to all near memory processors, a time at which a corresponding operation ends may vary. In an example, a required operation time of the near memory processor0141may be 6 and a required operation time of the near memory processor1151may be 10. In this example, the near memory processor0141may wait until an operation of the near memory processor1151ends. That is, an idle time of 4 may occur in the near memory processor0141. Therefore, it may be desirable to efficiently determine to which near memory processor an operation request received from a process is to be given. Accordingly, a method of determining a near memory processor to which an operation request is to be allocated based on state information of each near memory processor may be expected to reduce an idle time of each near memory processor and thereby achieve an increase in utilization of a near memory processor and a decrease in an operation time of a near memory processor.

FIGS.2A and2Billustrate examples of a state table, in accordance with one or more embodiments.

FIG.2Aillustrates the state table200, the near memory processors141,151,161, and171, priority score210, a write state220, a read state230, an operation size240, and a table identification number250.

In an example, the state table200may include state information related to a plurality of near memory processors respectively corresponding to memories. In an example, the state information may refer to information about current states of the near memory processors141,151,161, and171respectively corresponding to the individual memories. The processor may generate priority information based on the state information. Additionally, the processor may determine a near memory processor to process an operation request based on the priority information.

In an example, the state information may include at least one of priority information, write state information, read state information, operation size information, required operation time information, operation target data identification information, memory temperature information, and channel information.

In an example, the priority information may include information necessary to determine a near memory processor to process an operation request. The priority information may include the priority score210, and the processor may determine a near memory processor to process an operation request based on the priority score210. In an example, the priority score210of the near memory processor0141may be 5, the priority score210of the near memory processor1151may be 20, the priority score210of the near memory processor2161may be 0, and the priority score210of the near memory processor3171may be 15. The processor may allocate an operation request to the near memory processor1151with the highest priority score210.

In an example, the write state information may include information regarding whether a near memory processor is performing a write operation in a memory. In an example, when the near memory processor0141is performing a write operation in the memory0140, the write state220may be a “Busy” state. In an example, when the near memory processor1151is not performing a write operation in the memory1150, the write state220may be an “Idle” state.

In an example, the read state information may include information regarding whether a near memory processor is performing a read operation in a memory. In an example, when the near memory processor2161is performing a read operation in the memory2160, the read state230may be a “Busy” state. In another example, when the near memory processor1151is not performing a read operation in the memory1150, the read state230may be an “Idle” state.

In an example, the operation size information may include information about a size of operation to be performed by a near memory processor. The size of the operation may be determined based on a size of a batch allocated to a process. In an example, the size of the operation may be determined based on a number of indices referenced in a lookup table that is a target of operation. The operation size information may include the operation size240, and the near memory processor0141may be performing an operation with the operation size240of 120.

In an example, the operation time information may include time information calculated based on the operation size information. In an example, operation time information may include time information calculated based on the operation size information. The processor may calculate the required operation time information based on the operation size information, resource state information of a memory, and resource state information of a near memory processor.

In an example, the operation target data identification information may include information that identifies a plurality of tables divided from a single operation request. The operation request may be divided into the plurality of tables and may thereby be allocated to the plurality of near memory processors. Therefore, each piece of table identification information may be used in an example to aggregate operation results by the plurality of near memory processors. In an example, each piece of table may be required or necessary to aggregate operation results by the plurality of near memory processors. In an example, the operation target data identification information may include the table identification number250that is a target of operation. Still referring toFIG.2A, table identification numbers 1, 2, and 3 may represent table 1, table 2, and table 3 that are operation targets, respectively. Table 1, table 2, and table 3 may be tables that are targets of an operation request of the process1122. The near memory processor0141may operate operation target table 1, the near memory processor1151may operate operation target table 2, and the near memory processor2161may operate operation target table 3.

In an example, the operation target data identification information may include information to identify a plurality of tables divided from a single job request110. As described above with reference toFIG.1, the job request110may be divided into a plurality of batches. The plurality of batches may refer to the divided plurality of tables, respectively. Therefore, each piece of table identification information may be necessary to aggregate operation results by the plurality of near memory processors.

In an example, the memory temperature information may include information about each memory (or near memory processor). The processor may determine relatively low priority score for a near memory processor with relatively high temperature based on temperature information since an operation speed of the near memory processor with the high temperature may decrease. Therefore, an operation request of a process may selectively not be allocated to the near memory processor with relatively high temperature.

In an example, the channel information may include information about a channel connected to a memory. A memory channel may refer to a data transmission channel between a memory and a processor. In an example, at least one memory may be connected to a single channel. Additionally, the channel information may include memory slot information. A method of determining a near memory processor to process an operation request based on channel information is further described with reference toFIG.11, as a non-limiting example.

In an example, the processor may include at least one of write state information, read state information, operation size information, required operation time information, operation target data identification information, memory temperature information, and channel information from a status register of a near memory processor.

In an example, the priority information may include information that is determined based on write state information, read state information, required operation time information, operation size information, memory temperature information and/or channel information. That is, the processor may consider the write state information, the read state information, the required operation time information, operation size information, the memory temperature information and/or the channel information when determining a near memory processor to process an operation request of a process.

In an example, the priority information may include information that is determined by assigning a weight to the write state information and the read state information. The processor may determine the priority information by assigning a relatively high weight to the write state information and the read state information rather than the required operation time information, the operation size information, the memory temperature information and/or the channel information. In another example, the processor may primarily calculate the priority score210based on the write state information and the read state information. That is, the processor may determine a near memory processor to which an operation request of a process is to be allocated based on the write state information and the read state information. In an example, all of the plurality of near memory processors may have the same priority score210based on the write state information and the read state information of the plurality of near memory processors. When all the near memory processors have the same priority score210based on the write state information and the read state information, the processor may determine a near memory processor to which an operation request of a process is to be allocated based on the required operation time information, the operation size information, the memory temperature information and/or the channel information.

FIG.2Billustrates the write state220, the read state230, and score260, in accordance with one or more embodiments.

Referring toFIG.2B, in an example, if the write state220indicates an “Idle” state, the score260may be 15 points, if the write state220indicates a “Busy” state, the score260may be 0 points, if the read state230indicates an “Idle” state, the score260may be 5 points, and if the read state230indicates a “Busy” state, the score260may be 0 points. The score260may refer to an element score for each state used in a process of calculating the priority score210. In an example, “priority score210=write state score+read state score.” The processor may calculate the priority score210by summing up element scores for the respective states. In an example, Idle may represent that a write operation and/or a read operation is not being performed in a current memory. Additionally, “Busy” may represent that a write operation and/or a read operation is being performed in a current memory unit. In an example, Idle of the write state220may have a higher score than that of Idle of the read state230. When a near memory processor performs an operation request of a process, the near memory processor may initially perform the write operation before the read operation. Therefore, the near memory processor may need to initially perform the write operation to perform the operation request. Therefore, if the write state220is Idle, it may represent that the near memory processor may currently immediately perform the operation request of the process. If the write state220is Busy and the read state230is Idle, it may represent that the near memory processor may not currently immediately perform the operation request of the process and may need to wait. Therefore, a determination of whether to currently perform the write operation may be more important in determining priority information rather than a determination of whether to currently perform the read operation.

In an example, the processor may determine a near memory processor to which an operation request of a process is to be allocated based on the write state information and the read state information. In an example, the priority score210of the near memory processor0141in which the write state220indicates a “Busy” state and the read state230indicates an “Idle” state may be 5 points, the priority score210of the near memory processor1151in which the write state220indicates an “Idle” state and the read state230indicates an “Idle” state may be 20 points, the priority score210of the near memory processor2161in which the write state220indicates a “Busy” state and the read state230indicates a “Busy” state may be 0 points, and the priority score210of the near memory processor3171in which the write state220indicates an “Idle” state and the read state230indicates a “Busy” state may be 15 points. That is, the processor may determine the priority score210based on the write state220and the read state230. In this example, the processor may allocate the operation request of the process to the near memory processor1151with the highest priority score210.

In another example, the priority score210based on the write state information and the read state information may all be the same. In an example, all the near memory processors141,151,161, and171may have the write state220of Busy and the read state230of Idle and may all have the same priority score210as 5 points accordingly. In this example, the processor may determine a near memory processor to which an operation request of a process is to be allocated based on the required operation time information, the operation size information, the memory temperature information and/or the channel information.

FIG.3illustrates an example scheduler, in accordance with one or more embodiments.

FIG.3illustrates the job request110, a personalized recommendation model310, the process0121, the process1122, a process n320, an operator330, an instruction generator340, a memory request350, an instruction submission360, the scheduler130, an instruction370, a post-processing380, a plurality of memories140,150,160, and170, and an output390.

The personalized recommendation model310ofFIG.3is provided as an example only and various types of deep learning models may apply. In an example, the personalized recommendation model310may refer to a model that recommends information suitable to the desires of a user to the user. The processor may provide recommendation information to the user using the personalized recommendation model310and, to accordingly, may need to perform a deep learning operation. The processor may divide the job request110into a plurality of batches and may allocate the plurality of batches to each of the plurality of processes. The operation request of the process0121may be transmitted to the operator330of a near memory processor driver. The instruction generator340may generate an instruction based on information received from the operator330. When the instruction is generated, the memory request350that receives information about a memory to be implemented for operation may be made to the scheduler130. The processor may determine the memory1150(or the near memory processor1151) to process the operation request of the process0121by implementing the scheduler130. That is, the processor may determine the memory1150(or the near memory processor1151) to process the operation request of the process0121based on the priority information. The processor may transmit the instruction370to the memory1150that is to process the operation request. The near memory processor1151connected to the memory1150may process the operation request by executing the instruction370and may transmit operation results to the post-processing380. The processor may transmit again data generated by the post-processing380to the process0121and may acquire data of the output390.

In an example, the scheduler130may include a memory to store or storing a state table, for example, the state table200. The scheduler130may be processing circuitry, (e.g., as hardware, or a combination of hardware and instructions), that determines a near memory processor to process an operation request based on state information stored in the memory unit state table.

FIG.4illustrates an example operation process in a double buffer, in accordance with one or more embodiments.

FIG.4illustrates the process0121, the process1122, a read operation1410, write operation1420, a read operation2430, a read operation3440, and a write operation2450. InFIG.4, execution and write and read operations may refer to an operation performed by a near memory processor.

In an example, the near memory processor may process an operation request of a process in the double buffer. The double buffer may refer to a buffer structure that simultaneously stores and processes data. In an example, the double buffer may represent that the near memory processor may process data of a second buffer while storing data in a first buffer.

In an example, the near memory processor may perform a write operation and a read operation in a memory corresponding to the near memory processor. Performing the write operation and the read operation may include performing, by a single near memory processor, a write operation of a second process that is a succeeding process before a last read operation of a first process that is a preceding process. In an example, referring toFIG.4, the first process may be the process0121and the second process may be the process1122. Additionally, the last read operation of the first process may be the read operation1410and the read operation3440. The write operation of the second process may be the write operation1420and the write operation2450.

In an example, the read operation1410and the write operation1420may represent that the near memory processor may perform the first write operation1420of the process1122that is a succeeding process after the last read operation1410of the process0121that is a preceding process is terminated. In this example, an idle time may occur between execution of the process0121that is the preceding process and execution of the process1122that is the succeeding process. In response to the occurrence of the idle time, a total amount of time necessary for operation may unnecessarily increase. Therefore, it is possible to induce reduction in an operation time in a double buffer structure by preventing the occurrence of the idle time.

In an example, the read operation and the write operation may be distinguished from each other in the double buffer structure such that the read operation and the write operation may be simultaneously performed in the double buffer structure. Unless the read operation and the write operation are distinguished, the process1122that is the succeeding process may need to wait until the last read operation1410of the process0121that is the preceding process is terminated. In this example, the idle time may occur between the preceding process and the succeeding process.

In an example, the read operation and the write operation may be distinguished from each other in the double buffer structure such that the write operation of the process1121that is the succeeding process may be performed after the last write operation of the process0121that is the preceding process is terminated. In an example, in a state in which the last write operation of the process0121that is the preceding process is terminated, the write state220may be an idle state and the read state230may be a busy state. In this example, the process1122that is the succeeding process may be performed. Therefore, the first write operation2450of the process1122that is the succeeding process may be performed before the last read operation3440of the process0121that is the preceding process is performed. As another example, the first write operation2450of the process1122that is the succeeding process may be performed at the same time at which the last read operation3440of the process0121that is the preceding process is performed. The first write operation2450of the process1122that is the succeeding process may be performed simultaneously with the read operation2430of the process0121that is the preceding process or may be performed after the read operation2430is terminated. Therefore, the near memory processor may perform operation processing of each process without an idle time between execution of the process0121that is the preceding process and execution of the process1122that is the succeeding process.

FIG.5is a flowchart illustrating an example process scheduling method, in accordance with one or more embodiments. The operations inFIG.5may be performed in the sequence and manner as shown. One or more blocks ofFIG.5, and combinations of the blocks, can be implemented by special purpose hardware-based computer that perform the specified functions, or combinations of special purpose hardware and instructions, e.g., computer or processor instructions. In addition to the description ofFIG.5below, the descriptions ofFIGS.1-4are also applicable toFIG.5, and are incorporated herein by reference. Thus, the above description may not be repeated here for brevity purposes.

Referring toFIG.5, in operation510, a processor according to an example may prepare an instruction for an operation request of a process. When the instruction is ready in operation510, the processor may request a memory in operation520. In an example, requesting the memory in operation520may refer to requesting a near memory processor corresponding to the specific memory that is to process the operation request of the process. In operation530, the processor may select a near memory processor with high priority based on priority information. The processor may update state information about the near memory processor to which a job request is allocated. In operation531, the processor may update write state information included in a state table from an idle state to a busy state.

In operation540, the near memory processor may respond to the process. The near memory processor may notify the process that the operation request is received.

In operation550, the near memory processor may perform a write operation of writing an instruction to the particular memory.

In operation551, the processor may update operation size information included in the state table200. In operation552, the processor may update priority information included in the state table200.

In operation560, the near memory processor may perform an arithmetic operation. In an example, in a double buffer structure, the processor may update the write state that is updated with a busy state back to be an idle state after performing the arithmetic operation in operation560. Through this, the near memory processor may perform the write operation of the process1122ofFIG.4that is the succeeding process. When the arithmetic operation is completed, an operation of reading operation results may be performed. In operation561, the processor may update read state information of the near memory processor included in the state table200with a busy state.

When it is determined that the arithmetic operation is completed in operation570, the processor may update all of the write state information and the read state information with an idle state in operation571. As another example, in a double buffer structure, the processor may update only the read state with an idle state. In the double buffer structure, after performing operation560, the processor updates the write state that is updated with a busy state back to be an idle state and thus, may update only the read state with an idle state.

When it is determined that the arithmetic operation is not completed in operation570, the near memory processor may perform the arithmetic operation in operation560and may update read state information of the near memory processor included in the state table200with a busy state in operation561.

In operation580, the processor may perform a read operation of reading operation results from the specific memory.

FIG.6illustrates an example write operation of a near memory processor, in accordance with one or more embodiments.

FIG.6illustrates the plurality of processes121,122,123,124,125, and126, the scheduler130, a memory selection610, a state table620, the plurality of memories140,150,160, and170, and a write instruction630.

In an example, the processor may generate an instruction to perform an operation using a near memory processor. When the instruction is generated in parallel from the plurality of processes121,122,123,124,125, and126, the processor may determine a specific memory (or a near memory processor) that is to process an operation request using the scheduler130.

In an example, the processor may sequentially process an operation request of each process using the scheduler130.FIG.6illustrates an example in which an operation request of the process3124arrives first and is processed. The processor may receive the operation request of the process3124and may verify identification information about the process3124.

In an example, the processor may determine that the memory1150is available for the operation request of the process3124based on the priority information included in the state table620. That is, the processor may use the priority information included in the state table620for the memory selection610of selecting a memory that is available for the operation request of the process3124.

In an example, the processor may transmit, to the process3124, results information representing that the operation request of the process3124is allocated to the memory1150. The processor may write an instruction to a buffer of the near memory processor1151of the memory1150.

In an example, in response to performing the instruction write operation in the buffer, the processor may update state information included in the state table620.

In an example, after the write operation is completed, the processor may receive an operation request instruction from the process3124and may instruct the near memory processor1151of the operation request. Additionally, when the write operation is completed, the processor may update state information included in the state table620. As another example, in the double buffer structure, the processor may update a write state included in the state table620with an idle state in response to completion of the write operation.

FIG.7illustrates an example read operation of a near memory processor, in accordance with one or more embodiments.

FIG.7illustrates the plurality of processes121,122,123,124,125, and126, the scheduler130, a memory selection710, the state table620, the plurality of memories140,150,160, and170, an operation request completion status verification720, and a read instruction730.

In an example, in response to a request of the process3124, the processor may verify whether an operation is completed in the near memory processor1151. In an example, the processor may receive a request for the operation request completion status verification720from the process3124. In this example, the processor may verify whether the operation is completed by implementing a register included in the near memory processor1151.

In an example, when the operation is completed, the processor may read operation results of the near memory processor1151from the memory1150. The processor may read the operation results of the near memory processor1151from the memory1150by executing the read instruction730.

In an example, when the read operation is completed, the processor may update state information included in the state table620.

FIG.8illustrates an example process scheduling method when an instruction size is small, in accordance with one or more embodiments.

FIG.8illustrates the plurality of processes121,122,123,124,125, and126, the scheduler130, a memory selection810, the state table620, the plurality of memories140,150,160, and170, a write instruction820, and operation results830.

In an example, when a size of an operation request is less than a predetermined size, the processor may store the operation request in the scheduler130. An instruction may be generated based on the operation request of the process. The operation request may have various sizes and the instruction may also have various sizes.

In an example, the instruction may have a relatively large or small size. For example, when the size of the instruction is greater than the predetermined size, the processor may directly read and/or write the instruction outside the scheduler130as described above with reference toFIGS.1to7, and the processor may acquire only information about an available memory (or near memory processor) using the scheduler130. It may be efficient since, if a large-sized instruction is transmitted to the scheduler130, a bottleneck phenomenon may occur due to a bandwidth limitation.

In an example, when the size of the instruction is less than the predetermined size, the processor may transmit the instruction from the process to the scheduler130. In this example, although the instruction is transmitted, a bottleneck phenomenon may be less likely to occur. Therefore, the processor may receive the instruction from the process and may transmit the instruction to the scheduler130, and the processor may receive only operation results from the scheduler130. For example, the processor may receive the operation request of the process3124and may perform the memory selection810of selecting a memory to process the operation request. When the memory1150is selected, the processor may transmit the write instruction820to the scheduler130. The processor may transmit, to the near memory processor1151, the write instruction820stored in the scheduler130. The processor may read the operation results830of the near memory processor1151and may store the operation results830in the scheduler130. The processor may read the operation results830stored in the scheduler130and may transmit the same to the process3124.

In an example, since the processor may store an instruction and operation results in the scheduler130, the processor may queue the instruction for each near memory processor. The processor may improve utilization of a plurality of near memory processors by immediately allocating an operation request to an available near memory processor.

FIG.9illustrates an example process scheduling method when a number of processes is less than a number of memories, in accordance with one or more embodiments.

FIG.9illustrates the process0121, the process1122, the scheduler130, a memory selection910, the state table620, a write instruction920, and the plurality of near memory processors141,151,161, and171.

In an example, a number of processes may be less than a number of memories. In an example, referring toFIG.9, the number of processes is two, the process0121and the process1122, and the number of memories may be four, the memory0140, the memory1150, the memory2160, and the memory3170.

In an example, when the number of the plurality of processes is greater than the number of the plurality of near memory processors, the processor may allocate at least one operation request of a process to at least one near memory processor. In an example, the processor may receive three operation requests from the process1122. The processor may determine near memory processors to process the three operation requests by implementing the scheduler130. The processor may allocate the operation requests of the process1122to the near memory processor0141, the near memory processor1151, and the near memory processor2161based on priority information. In another example, the processor may receive a single operation request from the process1122and may receive a request for allocating a plurality of near memory processors to process a single operation request from the process1122. To process the single operation request, the processor may allocate the near memory processor0141, the near memory processor1151, and the near memory processor2161.

When the number of processes is greater than or equal to the number of memories, the processor may allocate an operation request to a near memory processor through the method described above withFIGS.1to7.

FIG.10illustrates an example process scheduling method when all near memory processors are performing an operation, in accordance with one or more embodiments.

FIG.10illustrates the process4125, the scheduler130, priority score1010, the state table620, the plurality of near memory processors141,151,161, and171, a required operation time1020of the near memory processor0141, a required operation time1030of the near memory processor1151, a required operation time1040of the near memory processor2161, and a required operation time1050of the near memory processor3171.

In an example, when all the near memory processors are performing an operation, the processor may determine a near memory processor that is expected to end first an operation request currently being processed based on required operation time information. In an example, the processor may receive an operation request of the process4125. The processor may allocate the operation request to a near memory processor based on the priority score1010included in state information. In an example, all the plurality of near memory processors141,151,161, and171may be performing an operation. In an example, the near memory processor0141may be processing an operation request of the process0121, the near memory processor1151may be processing an operation request of the process1122, the near memory processor2161may be processing an operation request of the process2123, and the near memory processor3171may be processing an operation request of the process3124. In this example, all the plurality of near memory processors may have the same priority score1010as 0. When all the near memory processors are performing an operation, the processor may determine a near memory processor to which an operation request is to be allocated based on required operation time information. The required operation time information may include time information that is calculated based on operation size information. In an example, the required operation time1020of the near memory processor0141may be 4, the required operation time1030of the near memory processor1151may be 2, the required operation time1040of the near memory processor2161may be 1, and the required operation time1050of the near memory processor3171may be 5. The processor may allocate the operation request of the process4125to the near memory processor2161that is expected to end first the operation. In an example, the near memory processor2161may process the operation request of the process4125after completing the operation request of the process2123currently being performed.

FIG.11illustrates an example process scheduling method when a plurality of near memory processors has the same priority, in accordance with one or more embodiments.

FIG.11illustrates the process4125, the scheduler130, priority score1130of the near memory processor2161and the near memory processor3171, the state table620, the plurality of near memory processors141,151,161, and171, a channel11110, and a channel21120.

In an example, when at least two near memory processors have the same priority based on priority information thereof, the processor may allocate operation requests to a near memory processor based on channel information of each of the near memory processors.

In an example, the processor may receive an operation request of the process4125. The processor may refer to the state table620included in the scheduler130. All the near memory processor2161and the near memory processor3171may have the highest priority score1130as 20 points. The near memory processor0141and the near memory processor1151may have the priority score1130of 0, and may not currently process the operation request. Therefore, the processor may allocate the operation request to one of the near memory processor2161and the near memory processor3171having the same priority score130. In this example, the processor may determine a near memory processor to which the operation request is to be allocated based on channel information of each of the near memory processor2161and the near memory processor3171. In an example, the near memory processor0141, the near memory processor1151, and the near memory processor2161may be included in the channel11110. Additionally, the near memory processor3171may be included in the channel21120. The near memory processor2161may be present in the same channel with the near memory processor0141and the near memory processor1151that are currently performing an operation. In this example, since operation results of the near memory processor0141and the near memory processor1151are being transmitted using the channel11110, a bottleneck phenomenon may occur when transmitting operation results of the near memory processor2161. Therefore, the processor may allocate a job request of the process4125to the near memory processor3171included in the channel21120that is not currently in use.

In an example, since a job request is allocated to a near memory processor using channel information, it is possible to prevent an operation processing time from increasing due to a bottleneck phenomenon that occurs when operation results of a plurality of near memory processors are transmitted and received through a single channel.