KR20250060052A - Method and apparatus for mapping memory for beam search - Google Patents

Abstract

A memory mapping method and device for beam search are provided. A memory mapping method according to one embodiment of the present invention is a memory mapping method for beam search in a computing system that uses mapping from a virtual address to a physical address to access a physical memory using a virtual address, the method comprising: when copying a first array defined on a virtual address to a second array, changing mapping information for a portion of the physical memory mapped to the second array that is to store data to be copied to point to a physical memory area mapped to the first array.

Description

{Method and apparatus for mapping memory for beam search}

The present invention relates to a memory mapping method and device for beam search.

Recently, as the inference performance of NLP (Natural Language Processing) for natural language processing has improved, NLP is being applied in various fields. In the case of Open-AI's GPT-3, it is being serviced as a chat GPT, and it is receiving a lot of attention because it generates sentences with natural expressions as if a person with expert knowledge is answering questions or instructions entered by a person, and it is being applied in various fields.

In GPT, a representative NLP algorithm, when a user inputs a sentence such as “It is nice,” a dictionary operation is performed to calculate the score value of each word in order to generate the next word from the sentence “It is nice.” The information obtained through the dictionary operation is applied to each word registered in the word dictionary (vocabulary set) to calculate the score value for each word. The word with the highest score value among the calculated score values is selected and output.

For example, when applying the score values to all words in the sentence “It is nice”, the word “to” has the highest score value, so “to” is output. In order to guess the word that can come after “to”, the currently output word “to” is token embedding, and the same process is repeated to output the next word “meet”, and the same process is repeated to generate “you” from the word “meet”. This process is repeated until the token indicating the end of the sentence is selected as the output token.

In this process of generating output sentences one word at a time by repeatedly doing so, the influence of the word that comes next after the current word is not considered, so after generating the entire sentence, the problem of performance degradation occurs compared to when generating sentences by considering all cases. This is because even if the word with the highest score is selected when selecting an individual word, the score value obtained by selecting this word may not be the global maximum but the local maximum.

However, generating sentences by considering all possible combinations increases the computational amount unrealistically. For example, if you look at GPT-2, whose variable values are public, 50,257 words are registered in the vocabulary set. Therefore, in order to output a word, you have to calculate the score value for each of the 50,257 words and then go through the process of selecting the word with the highest score value as the output value.

For this reason, instead of generating only one output word for each individual word generation, a beam search method is applied that maintains the B words with the highest score values as output candidates.

When beam search is applied, instead of outputting only one word for each word position, it outputs k words with the highest scores among the words in the vocabulary set, generates k words at the next word positions for each sentence with k different paths, and then retains k sentences with the highest final cumulative recognition performance (score) value as output candidates.

That is, when applying beam search with beam width B, at each word generation, the words with the B highest score values that can be selected at the current position are selected as candidates from each of the B previously selected candidate sentences, and the B sentences with the highest score among the total B ^two candidates are selected as the output sentence. In this way, the amount of data that needs to be stored increases in proportion to the square of the beam width.

In the past, when applying beam search, the feature data required for each selected individual sentence was stored in memory. This case has the advantage of easy software implementation, but even if there is a part consisting of the same combination of words among several generated candidate sentences, the feature data corresponding to that location is not shared, and each value is stored in an independent location in the memory, so there is a problem of high memory bus bandwidth usage for memory read/write.

To improve these problems, a linked list type data structure can be used and a method can be used to manage the feature data added to each word due to the word. However, if implemented in this way, the implementation of software that implements parallel processing using multiple processors becomes complicated, and since the data structure is stored in a different form from the one supported by general-purpose DMA (Direct Memory Access), the process of retrieving it from external memory using general-purpose DMA becomes complicated or there are implementation restrictions.

In a computing system that uses virtual addresses, memory is divided into blocks (pages) of a certain size, and the virtual address area and the physical address area are mapped for each block. When a virtual address is divided into pages, the page number is called a VPN (virtual page number), and when physical memory is divided into pages, the page number is called a PPN (physical page number).

When using a memory space as large as the beam width in the virtual address space, each memory area must be mapped to the actual memory. When a computing system attempts to perform a read/write operation on memory using an address value for the virtual address space, the given virtual address is converted to the start address of the corresponding page in the physical memory by referring to the VPN to PPN mapping table, and then the address that needs to access the actual memory is generated using the address offset within the page and the necessary operation can be performed.

In the conventional technology, even if multiple beams have parts of feature data that have common values, they are operated in a form where the same values are copied and stored in different spaces of the actual physical memory. Therefore, the memory space and memory bus bandwidth are used inefficiently.

The present invention aims to provide a memory mapping method and device for beam search, which can eliminate the inefficiency of copying the same data multiple times for pages storing the same data among a plurality of candidate sentences when processing NLP using beam search in a computing system using a virtual address space.

The purpose of the present invention is to provide a memory mapping method and device for beam search that can minimize degradation of NLP processing performance due to bandwidth limitations of external memory when storing feature data in an external memory during a beam search application process.

A memory mapping method according to one embodiment of the present invention is a memory mapping method for beam searching in a computing system that uses mapping from a virtual address to a physical address to access a physical memory using a virtual address, the method comprising: when copying a first array defined on a virtual address to a second array, changing mapping information for a portion of the physical memory mapped to the second array that is to store data to be copied to point to a physical memory area mapped to the first array.

In a case where mapping from a virtual address to a physical memory is performed on a page basis and the start address value of the first array is limited to a multiple of the page size, a memory mapping method according to an embodiment of the present invention includes a step of updating only VPN to PPN mapping information for pages having the same value among pages mapped to the first array, and, in a case where even some data in a page is different, reading the value from a physical page mapped to the first array and copying it to a physical page mapped to the second array.

In a case where mapping from a virtual address to a physical memory is performed on a page basis and the start address value of the first array is limited to a multiple of the page size, a memory mapping method according to an embodiment of the present invention may include a step of updating only VPN to PPN mapping information for pages except the last page among the pages mapped to the first array, and, for the last page, if the last page has data as full as the page size, updating only the VPN to PPN mapping information, and otherwise, reading values from a physical page mapped to the first array and copying them to a physical page mapped to the second array only for data stored in the last page.

The computing system may include a PPN information table that stores information about the number of VPNs mapped to one PPN. A memory mapping method according to one embodiment of the present invention may include a step of decreasing the number of VPNs mapped to a specific PPN in the PPN information table by 1 for an array that is no longer used among arrays copied to a specific PPN, and a step of adding the corresponding PPN to a free PPN list that manages pages that are not currently in use when the number of VPNs mapped to the PPN becomes 0 as a result of the decrease.

In a case where the computing system supports various page sizes, a memory mapping method according to one embodiment of the present invention may include a step of converting the size of a page mapped to the first array to a page of a small size and copying the data to a page allocated to the second array, when the last page of the first array is set to a large-sized page but the size of data contained in the last page is small.

In a case where a computing system supports various page sizes, a memory mapping method according to an embodiment of the present invention may include a step of allocating a page of a relatively small size to the last page in a process of copying feature data generated in a context stage as many times as the number of beams when performing an operation applying beam search of NLP (Natural Language Processing) in the computing system.

In a case where a computing system supports various page sizes, a memory mapping method according to an embodiment of the present invention may include a step of selecting and using a page size having a size equal to or a multiple thereof of the size of feature data added for each word generated in a generation phase.

In a computing system using a mapping from a virtual address to a physical address to access a physical memory using a virtual address, a memory mapping device for beam search according to one embodiment of the present invention is configured such that, when copying a first array defined on a virtual address to a second array, the matching device can change mapping information regarding a portion of the physical memory mapped to the second array that is to store data to be copied to point to a physical memory area mapped to the first array.

In one embodiment, the memory mapping device has a VPN to PPN mapping table for storing mapping information from a VPN to a PPN. When mapping from a virtual address to a physical memory is performed in units of pages and a start address value of a first array is limited to a multiple of a page size, the memory mapping device updates only the VPN to PPN mapping information for pages having the same value among pages mapped to the first array, and when there is a part of data that is different in one page, the memory mapping device reads the value from the physical page mapped to the first array and copies it to the physical page mapped to the second array.

In one embodiment, the memory mapping device includes a PPN information table that stores information about the number of VPNs mapped to one PPN, and a free PPN list that manages pages that are not currently in use. The memory mapping device decreases the number of VPNs mapped to a specific PPN in the PPN information table by 1 for an array that is no longer in use among the arrays copied to the specific PPN, and when the number of VPNs mapped to the PPN becomes 0 as a result of the decrease, the memory mapping device can add the corresponding PPN to the free PPN list.

In a computing system supporting various page sizes, when the last page of the first array is set to a large-sized page but the size of data contained in the last page is small, a memory mapping device according to an embodiment of the present invention can convert the size of a page mapped to the first array to a small-sized page and copy the data to a page allocated to the second array.

In a computing system supporting various page sizes, when performing an operation applying beam search of NLP (Natural Language Processing) in the computing system, a memory mapping device according to an embodiment of the present invention supports various page sizes, and in the process of copying feature data generated in a context stage by the number of beams, a page of a relatively small size can be allocated to the last page.

In a computing system that supports various page sizes, a memory mapping device according to one embodiment of the present invention can select and use a page size that is the same size as or a multiple of the size of feature data added for each word generated in a generation phase if there is a page.

In one embodiment, the first array may be feature data generated in the context phase, and the second array may be feature data in the generation phase.

According to one embodiment of the present invention, unnecessary memory read/write processes can be reduced by only updating information in a mapping table that converts a virtual address into a physical address.

According to one embodiment of the present invention, when storing feature data in an external memory during a beam search application process, external memory access is not performed for shareable data through page table mapping information update, and external memory access is performed only for non-shareable areas, thereby minimizing degradation of NLP processing performance due to bandwidth limitations of the external memory.

According to one embodiment of the present invention, since the phenomenon of the processing speed of the AI accelerator chip being reduced due to external memory bandwidth limitations can be minimized, the data processing performance that can be processed per unit time through the AI accelerator chip is improved.

Figure 1 is a block diagram showing the hardware configuration of an AI accelerator (100) using a virtual address space.
Figure 2 shows an example of B memory areas being mapped to actual physical memory on a virtual address when beam search is applied to GPT in a conventional computing system.
FIG. 3 is a drawing showing a memory operating method according to the method of the present invention.
FIG. 4 shows the difference between applying the existing method and the method proposed in the present invention when managing resource usage and mapping information on a page basis in a computing system supporting a virtual address space.
FIG. 5 is a flowchart showing an operation of managing the number of VPNs mapped to each individual physical page in one embodiment of the present invention.
FIG. 6 is a drawing for explaining how to variably adjust the size of a page so that efficient data sharing can be achieved when copying feature data to a sequence information table in one embodiment of the present invention.

Hereinafter, some embodiments of the present disclosure will be described in detail using exemplary drawings. When adding reference numerals to components of each drawing, it should be noted that the same numerals are used for identical components as much as possible even if they are shown in different drawings. In addition, when describing the present disclosure, if it is determined that a specific description of a related known configuration or function may obscure the gist of the present disclosure, the detailed description thereof will be omitted.

In describing components of embodiments according to the present disclosure, symbols such as first, second, i), ii), a), b), etc. may be used. These symbols are only for distinguishing the components from other components, and the nature, order, or sequence of the corresponding components are not limited by the symbols. When a part in the specification is said to 'include' or 'provide' a component, this does not mean that other components are excluded, but rather that other components can be further included, unless explicitly stated to the contrary. In addition, terms such as 'part' and 'module' described in the specification mean a unit that processes at least one function or operation, and this can be implemented by hardware, software, or a combination of hardware and software.

The following description of the invention, together with the accompanying drawings, is intended to explain exemplary embodiments of the invention and is not intended to represent the only embodiments in which the invention may be practiced.

In a computing system that uses a mapping from a virtual address to a physical address to access a physical memory using a virtual address, when copying a first array defined on a virtual address to a second array, instead of reading a value stored in the first array from memory and storing it in a memory mapped to the second array, the present invention changes mapping information for a portion of the physical memory mapped to the second array where data to be copied is to be stored to point to a physical memory area mapped to the first array. This method can be configured to be executed only when a condition is met that no data is modified for the portion copied from the first array when using it after copying array B.

In one embodiment, when mapping from a virtual address to a physical memory is performed on a page basis and the start address value of the first array is limited to a multiple of the page size, only the VPN to PPN mapping information is updated for pages that have the same value among the pages mapped to the first array, and when there is a part of data that is different even within a page, the value can be read from the physical page mapped to the first array and copied to the physical page mapped to the second array.

In a case where mapping from a virtual address to a physical memory is performed on a page basis and the start address value of the first array is limited to a multiple of the page size (i.e., data is aligned on a page basis), in one embodiment of the present invention, only VPN (virtual page number) to PPN (physical page number) mapping information can be updated for pages except the last page among the pages mapped to the first array. For the last page, if the last page is filled with data as much as the page size, only the VPN to PPN mapping information (VPN to PPN mapping information) is updated. If the last page is not filled with data as much as the page size, only for the data stored in the last page, the values are read from the physical page mapped to the first array and actually copied to the physical page mapped to the second array.

On the other hand, if the starting address value of the first array is not limited to a multiple of the page size, in one embodiment of the present invention, data is directly copied to the physical pages mapped to the second array for the first and last pages among the pages mapped to the first array, and only the mapping information from the VPN to the PPN can be updated for the remaining pages.

In some embodiments, a table may be included that stores information about the number of VPNs mapped to a PPN. When one of the arrays copied to a specific PPN is no longer in use, the number of VPNs mapped to the specific PPN in the table is decreased by 1. When the number of VPNs mapped to the PPN becomes 0 as a result of this decrease, the PPN is added to a free PPN list that manages pages that are not currently in use.

The computing system according to the present invention can support various page sizes. In this case, if the last page of the first array is set to a large-sized page while the size of data contained in the last page is small, the size of the page mapped to the first array can be converted to a small-sized page and the data can be copied to the page allocated to the second array. Accordingly, when the valid data stored in the second array increases through a subsequent operation process, the number of pages filled with data can be increased and the amount of data contained in the last page with only a portion of the data can be reduced, thereby minimizing the overhead of copying data when copying the second array to the third array later.

In order to improve the performance of NLP (Natural Language Processing) in a computing system supporting various page sizes, when performing an operation applying beam search, in one embodiment of the present invention, in the process of copying feature data generated in a context step by the number of beams, a large-sized page can be allocated to the front feature data and a small-sized page can be allocated to the back-most feature data according to the size of the feature data generated in the context.

In a computing system that supports various page sizes, in one embodiment of the present invention, if there is a page having the same size as the size of feature data added for each word generated in the generation phase or a page having a size corresponding to a multiple thereof, the corresponding page size can be selected and used.

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the drawings.

Fig. 1 shows the hardware configuration of an AI accelerator (100) that uses a virtual address space. The AI accelerator (100) includes a processor (110), a TLB (Translation Lookaside Buffer) (130) that stores information for conversion from a virtual address to a physical address, and an MMU (memory management unit) (120) that converts a virtual address from the processor (110) to a physical address by referring to the TLB (130). The AI accelerator (100) also includes an operation unit (150) that performs various operation operations, and a DMA (Direct Memory Access) (140) that allows the operation unit (150) to directly access a memory (200).

When the processor (110) attempts to access memory (200) such as DRAM using a virtual address, the MMU (120) converts the virtual address into a physical address by referring to the TLB (130). Through this, the processor (110) can perform a read/write operation on the memory (200). The DMA (Direct Memory Access) (140) and the operation unit (150) within the AI accelerator (100) directly access the memory (200) using a physical address.

Among the feature data for individual beams, there may be parts that have the same values. For example, there are feature data (K, V) generated in the context phase, and cases where the same word sequence is present among multiple beams when generating sentences in the generation phase.

In one embodiment of the present invention, when mapping is performed to physical pages on a page-by-page basis in a computing system using virtual addresses, instead of physically allocating different pages and copying data for pages having the same value, only the mapping information from VPN to PPN is updated so that different virtual pages point to the same physical page, thereby minimizing the amount of read/write to external memory.

Fig. 2 shows an example of B memory areas being mapped to actual physical memory on a virtual address when beam search is applied to GPT in a conventional computing system. Pages marked in gray in the physical memory represent pages that have the same data among the B arrays (va_0 to va_(B-1)), and the pages in the last part of each array are hatched only for some areas that contain data among the pages. Since the B beams have different data in the corresponding parts, the gray background is indicated in different shades.

The situation shown in Fig. 2 is the initial stage where the context phase ends and the generation phase begins in the GPT, or the case where the currently selected B words are connected to the same word sequence during the generation phase. The parts that contain data in the actual physical memory page space are indicated by hatching and shading, and the shading intensity is indicated differently to indicate that each beam has different data.

In conventional systems, even if multiple beams have parts of feature data that have common values, they are operated in a form where the same values are copied and stored in different spaces of the actual physical memory, as shown in Fig. 2, which results in inefficient use of memory space and memory bus bandwidth.

FIG. 3 is a diagram showing a memory operating method according to the method of the present invention. As illustrated in FIG. 3, in the present invention, pages having the same data among multiple beams are shared during a beam search operation process for GPT, thereby reducing memory space and memory bus bandwidth usage. That is, when storage space for B beams is being used on a virtual address, memory space is efficiently used by setting a mapping table so that VPN to PPN mapping accesses the same physical page for parts having common data on the B beams.

When the feature data stored in the memory in the first beam va_0 in Figure 3 is divided into pages, the parts that have the same values as other beams and can be shared are marked in gray in the physical memory, and pages that cannot be shared with other beams are marked with a hatched area.

In the example of FIG. 3, the three pages of va_0 are identical to va_1, ..., va_(B-1), but the last page of va_0 has some data that has the same values as other beams and some data that has different values. In the present invention, in a computing system using a virtual address space, pages that have the same values can be shared between multiple beams by modifying the mapping information from VPN to PPN during the mapping process for each page. Therefore, in a case where all data in one page block can be shared, sharing is possible between multiple beams by modifying the mapping information, but in a case where even some data in one page is different, as in the case of the last page of va_0, sharing for each page is not possible, and therefore data is stored using physically different pages between each beam.

In the case of the second beam va_1 in Fig. 3, except for the last page, all other pages are mapped to the part used as a physical page in va_0, and only the very last page with a different value is mapped to a different page in physical memory. This mapping is applied equally up to va_(B-1).

In one embodiment, for the last page, if the last page has data as full as the page size, only the mapping information from the VPN to the PPN is updated, and otherwise, only for the data stored in the last page, the values are read from the physical page mapped to the first array and copied to the physical page mapped to the second array.

FIG. 4 shows the difference between a conventional method and a method according to an embodiment of the present invention when managing resource usage and mapping information on a page basis in a computing system supporting a virtual address space.

Fig. 4 (a) shows information for conventional page management. When physical memory is divided into page units, it consists of a free PPN list (420) that manages index information for pages that are not yet used, and a VPN to PPN mapping table (410) that indicates which physical page a virtual page is mapped to. Typically, an operating system (OS) manages this information. When a user program wants to access memory, a process of converting to a physical address is performed through this VPN to PPN mapping table (410). In order to process this process quickly, a memory management unit (MMU) is sometimes included in the hardware.

When a user program requests memory to use data in the virtual address space, the OS maps a physical page in the free PPN list (420) to the requested virtual address. In addition, when the user program no longer uses the memory and the page becomes free, the OS deletes the mapped information and puts the index values for the physical pages that were used back into the free PPN list (420) so that they can be used when another memory allocation request comes in.

Figure 4 (b) shows information for managing page tables according to the method of the present invention. For the same purpose as the conventional method, a free PPN list (420) and a mapping table (410) from VPN to PPN are used, and additionally, a PPN information table (PPN info table) (430) is used to manage the number of virtual pages mapped to physical pages.

In the case where multiple VPNs are mapped to one PPN and used, even if a memory free request comes in from some of the mapped VPNs, if there is at least one VPN mapped to the physical page, the physical page should be marked as still in use. To this end, the number of VPNs mapped to each physical page is managed using the PPN information table (430). That is, as illustrated in FIG. 5, when a memory free request comes in from a mapped VPN (step S10), the number of VPNs mapped to the physical page in the PPN information table (430) is decreased by the number of VPNs for which a memory free request has come in (step S20). If the number of VPNs mapped to the physical page becomes 0 as a result of the decrease ('Yes' in step S30), the physical page is added to the free PPN list (420) (step S40).

FIG. 6 shows that the page size is variably adjusted so that efficient data sharing is possible when copying feature data to a sequence information table by applying the method proposed in the present invention. In the case of GPT, feature data is generated in the context phase according to the user's question, and an output sentence for the user's question is generated in the generation phase. In the case of GPT-3, the feature data generated per word (token) corresponds to one row in the K, V matrices, and the size of the data for one row is approximately 8 kB. At this time, since it is possible to receive and apply all of the user's questions at once in the context phase, it may be advantageous to select a large page size and allocate memory space in order to increase the TLB (Translation Lookaside Buffer) hit of the MMU (Memory Management Unit) during the mapping process from VPN to PPN.

On the other hand, in the generation step, only one word is generated at a time and feature data is added, and in order to share information about multiple beams, using pages that match the sizes of pad_K and pad_V, which are feature data generated for each word, can increase the probability of data sharing and reduce physical data copying. To this end, in one embodiment of the present invention, if there is a page that is the same size as or a multiple of the size of feature data added for each word generated in the generation step, the corresponding page size can be selected and used.

In Fig. 6, when transitioning from a context phase in which memory allocation is performed using a large-sized page to a generation phase, in order to efficiently perform physical page sharing through mapping from a VPN to a PPN according to the method of the present invention, the last page is converted to a relatively small-sized page unless it is full of feature data. In addition, empty pages that do not yet contain data but are allocated to an array can also be changed to small-sized pages.

In addition, when copying the first array defined on the virtual address to the second array, if the last page of the first array is set to a large-sized page but the size of the data contained in the last page is small, the size of the page mapped to the first array can be converted to a small-sized page and the data can be copied to the page allocated to the second array. By configuring it this way, when the valid data stored in array B increases through a later operation process, the number of pages full of data can increase and the amount of data for the last page containing some data can be reduced, thereby minimizing the overhead for copying data when copying the second array to the third array later.

According to one embodiment of the present invention, when copying feature data is performed whenever beam information changes in the inference process of NLP applying beam search, the amount of reading/writing to actual memory is minimized, thereby alleviating the problem of performance of AI accelerator being limited due to limitations in memory bus bandwidth.

In the case of GPT-3, each row of the K and V matrices is about 8kB in size. When a user's question is received, feature data is generated in the context phase for the number of corresponding words (K and V matrices with as many rows as the number of words), and in the generation phase, one row is added to the end of each K and V matrix for each word generated, and as the total number of tokens increases, the size of the feature data to be copied continues to increase.

Conventionally, a method has been taken to physically copy all feature data, but since the maximum number of tokens supported by GPT-3 is 2049 to 8001, the maximum feature data size increases to 32 to 125 MB (the size of the two matrices K and V), and in the worst case, copying is performed a number of times corresponding to the beam width.

In one embodiment of the present invention, since data copying occurs only for the last page, even if the total number of tokens increases as the generation step progresses, in the worst case, only the data corresponding to the last page is copied, so that the memory bus bandwidth usage can be reduced much more effectively than in the conventional method, and the NLP performance that can be processed per unit time in the AI accelerator can be increased.

Each component of the device or method according to the present invention may be implemented as hardware or software, or as a combination of hardware and software. In addition, the function of each component may be implemented as software, and a microprocessor may be implemented to execute the function of the software corresponding to each component.

Various implementations of the systems and techniques described herein can be implemented as digital electronic circuits, integrated circuits, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include implementations of one or more computer programs executable on a programmable system. The programmable system includes at least one programmable processor (which may be a special purpose processor or a general purpose processor) coupled to receive data and instructions from, and transmit data and instructions to, a storage system, at least one input device, and at least one output device. Computer programs (also known as programs, software, software applications, or code) include instructions for the programmable processor and are stored on a "computer-readable medium."

A computer-readable recording medium includes any type of recording device that stores data that can be read by a computer system. Such a computer-readable recording medium can be a non-volatile or non-transitory medium, such as a ROM, a CD-ROM, a magnetic tape, a floppy disk, a memory card, a hard disk, a magneto-optical disk, a storage device, and may further include a transitory medium, such as a data transmission medium. In addition, the computer-readable recording medium can be distributed over a network-connected computer system, so that the computer-readable code can be stored and executed in a distributed manner.

Although the flowchart of this specification describes each process as being executed sequentially, this is only an illustrative description of the technical idea of one embodiment of the present disclosure. In other words, a person having ordinary skill in the art to which one embodiment of the present disclosure belongs may change the order described in the flowchart of this specification without departing from the essential characteristics of one embodiment of the present disclosure, or may modify and modify and apply various modifications and variations such as executing one or more of the processes in parallel. Therefore, the flowchart of this specification is not limited to a chronological order.

The above description is merely an example of the technical idea of the present embodiment, and those skilled in the art will appreciate that various modifications and variations may be made without departing from the essential characteristics of the present embodiment. Accordingly, the present embodiments are not intended to limit the technical idea of the present embodiment, but rather to explain it, and the scope of the technical idea of the present embodiment is not limited by these embodiments. The protection scope of the present embodiment should be interpreted by the following claims, and all technical ideas within a scope equivalent thereto should be interpreted as being included in the scope of the rights of the present embodiment.

100 AI accelerators,
110 processor,
120 Memory Management Units (MMUs);
130 Translation Lookaside Buffer (TLB),
140 DMA (Direct Memory Access),
150 operation units,
200 External memory.

Claims (16)

A memory mapping method for beam searching in a computing system that uses a mapping from a virtual address to a physical address to access physical memory using a virtual address,
When copying a first array defined on a virtual address to a second array, a step of changing the mapping information for a portion of the physical memory mapped to the second array that will store the data to be copied to point to the physical memory area mapped to the first array
A memory mapping method for beam search having a .
In the first paragraph,
Mapping from virtual addresses to physical memory is done on a page-by-page basis.
In the case where the start address value of the first array is limited to a multiple of the page size, only the VPN to PPN mapping information is updated for pages that have the same value among the pages mapped to the first array, and in the case where there is a part of data that is different in one page, a step of reading the value from the physical page mapped to the first array and copying it to the physical page mapped to the second array.
A memory mapping method for beam search, comprising:
In the first paragraph,
Mapping from virtual addresses to physical memory is done on a page-by-page basis.
If the starting address value of the first array is limited to a multiple of the page size,
For pages except the last page among the pages mapped to the first array, only the VPN to PPN mapping information is updated.
For the last page, if the last page has data as full as the page size, only the mapping information from VPN to PPN is updated, and if not, only for the data stored in the last page, a step of reading the value from the physical page mapped to the first array and copying it to the physical page mapped to the second array.
A memory mapping method for beam search, comprising:
In the second or third paragraph,
The above computing system includes a PPN information table that stores information about the number of VPNs mapped to one PPN,
A step of decreasing the number of VPNs mapped to the specific PPN in the PPN information table by 1 for arrays that are no longer used among the arrays copied to the specific PPN,
A memory mapping method for beam search, comprising the step of adding the PPN to a free PPN list that manages pages that are not currently in use when the number of VPNs mapped to the PPN becomes 0 as a result of the above reduction.
In claim 2 or 3, the computing system supports various page sizes,
A memory mapping method for beam search, comprising the step of converting the size of a page mapped to the first array into a page of a small size and copying the data to a page allocated to the second array when the last page of the first array is set to a large-sized page but the size of data contained in the last page is small.
In claim 2 or 3, the computing system supports various page sizes,
A memory mapping method for beam search, comprising a step of allocating a page of a relatively small size to the last page in the process of copying feature data generated at the context stage as many times as the number of beams when performing an operation applying beam search of NLP (Natural Language Processing) in the above computing system.
In the second or third paragraph,
The above computing system supports various page sizes,
A memory mapping method for beam search, comprising a step of selecting and using a page size that is the same as or a multiple of the size of feature data added for each word generated in the generation phase.
In the second or third paragraph,
The first array is the feature data generated in the context stage.
The second array is the feature data from the generation stage.
Memory mapping method for beam search.
A memory mapping device for beam searching in a computing system that uses a mapping from virtual addresses to physical addresses to access physical memory using virtual addresses,
The above matching device changes the mapping information for the part of the physical memory mapped to the second array that will store the data to be copied when copying the first array defined on the virtual address to the second array to point to the physical memory area mapped to the first array.
Memory mapping device for beam search.
In Article 9,
The above memory mapping device has a VPN to PPN mapping table for storing mapping information from a VPN to a PPN.
Mapping from virtual addresses to physical memory is done on a page-by-page basis.
In the case where the start address value of the first array is limited to a multiple of the page size, the memory mapping device updates only the VPN to PPN mapping information for pages that have the same value among the pages mapped to the first array, and in the case where there is a part of data that is different in one page, the value is read from the physical page mapped to the first array and copied to the physical page mapped to the second array.
Memory mapping device for beam search.
In Article 9,
The above memory mapping device has a VPN to PPN mapping table for storing mapping information from a VPN to a PPN.
Mapping from virtual addresses to physical memory is done on a page-by-page basis.
The above memory mapping device updates only the VPN to PPN mapping information for pages except the last page among the pages mapped to the first array.
For the last page, if the last page has data as full as the page size, only the mapping information from VPN to PPN is updated, otherwise, only for the data stored in the last page, the values are read from the physical page mapped to the first array and copied to the physical page mapped to the second array.
Memory mapping device for beam search.
In clause 10 or 11,
The above memory mapping device includes a PPN information table that stores information about the number of VPNs mapped to one PPN, and a free PPN list that manages pages that are not currently in use.
The above memory mapping device decreases the number of VPNs mapped to the specific PPN in the PPN information table by 1 for arrays that are no longer used among the arrays copied to the specific PPN.
As a result of the above reduction, when the number of VPNs mapped to the PPN becomes 0, the memory mapping device adds the PPN to the free PPN list.
Memory mapping device for beam search.
In clause 10 or 11,
The above computing system supports various page sizes,
If the last page of the first array is set to a large-sized page, but the size of the data contained in the last page is small, the memory mapping device converts the size of the page mapped to the first array to a small-sized page and copies the data to the page allocated to the second array.
Memory mapping device for beam search.
In clause 10 or 11,
The above computing system supports various page sizes,
When performing an operation applying beam search of NLP (Natural Language Processing) in the above computing system, the memory mapping device supports various page sizes, and in the process of copying the feature data generated in the context stage to the number of beams, a page of a relatively small size is allocated to the last page.
Memory mapping device for beam search.
In clause 10 or 11,
The above computing system supports various page sizes,
The above memory mapping device selects and uses a page size that is the same as or a multiple of the size of the feature data added each time a word is generated in the generation phase, if there is a page with the same size as or a multiple of the size of the feature data.
Memory mapping device for beam search.
In clause 10 or 11,
The first array is the feature data generated in the context stage.
The second array is the feature data from the generation stage.
Memory mapping device for beam search.

Images