KR102179399B1 - Smart i/o stream detection based on multiple attributes - Google Patents

Abstract

The multi-streaming memory system includes a memory and a processor connected to the memory, the processor executing a software component, each associated with a logic block address, each corresponding to each of a plurality of streams of data writes Identify a plurality of attributes, evaluate the importance coefficient for each of the attributes corresponding to each of the streams, and based on each of the logic block addresses and all the importance coefficients for the assigned stream, the logic block Two or more of the logical block addresses are clustered by assigning a stream ID to each of the addresses.

Description

Smart input/output stream detection based on various properties {SMART I/O STREAM DETECTION BASED ON MULTIPLE ATTRIBUTES}

The present invention relates to methods and mechanisms for improving stream allocation in multi-streaming flash drives.

A solid-state drive/solid-state disk (SSD) is a solid-state storage device that continuously stores data using integrated circuit (IC) assemblies as memory. SSD technology typically uses electronic interfaces that are compatible with existing block input/output (I/O) hard disk drives (HDDs), providing easy replacement for many common applications.

Write amplification describes a problem corresponding to some types of nonvolatile memory, such as NAND flash memory used in solid state drives (SSDs). Write amplification can be described as the ratio of the number of writes committed to the nonvolatile memory in the SSD and the number of writes coming from the host computing platform. Write amplification can cause problems for random writes to the SSD. For example, high write amplification may reduce write performance to an SSD, increase wear of nonvolatile memory cells, and thus degrade durability of a memory device.

The concept called "multi-stream SSD" provides operating systems and applications with interfaces that individually store data with different attributes. These individual data stores are referred to as "streams." Streams can be used to indicate when different data writes are associated with each other or have a similar lifetime. That is, a group of individual data writes may be part of an aggregate stream, and each stream is identified by a stream ID assigned by the operating system or the corresponding application. Thus, different data having similar characteristics or attributes are assigned a unique stream ID so that data corresponding to that stream ID can be written to the same block in the SSD.

That is, multi-streaming flash drives enable more flexibility by placing related write operations together on SSDs, thereby reducing write amplification and improving performance of SSDs. For example, efficient stream allocation in multi-streaming flash drives can reduce write amplification and improve both lifespan and durability of SSDs.

Currently, stream allocation generally occurs at the application layer by modifying the application performing data writes, which in turn results in systems with multiple instances of different applications due to high maintenance overhead. May not be suitable. Also, when multiple applications are supported by multiple storage devices at the backend, the associated overhead further increases.

Also, in most of the current multi-streaming systems, only a few attributes (i.e., frequency and temporal locality attributes of access of a particular entity) are used for automatic stream detection, so streams are The method of analysis to detect is limited.

Accordingly, the present invention provides multi-streaming flash drives, in particular to reduce write amplification, and to improve the performance of solid state drives (SSDs).

According to an embodiment of the present invention, a multi-streaming memory system includes a memory and a processor connected to the memory, and the processor executing a software component is associated with each of the logic block addresses, each writing data Identifying a plurality of attributes corresponding to each of a plurality of streams of, evaluating an importance coefficient for each of the attributes for each of the streams, and all importance for each of the logical block addresses and the assigned stream Two or more logical block addresses are clustered by assigning a stream ID to each of the logical block addresses based on coefficients.

The software component further comprises assigning a weighting factor to one or more attributes, wherein the software component is based on the assigned weighting factor to the importance coefficients corresponding to the plurality of attributes rather than other importance coefficients. Priority is given and the stream ID is assigned to the logical block addresses.

The software component generates an nXm feature matrix containing nXm addresses to evaluate the importance factor for each of the attributes for each of the logical block addresses, where n is the total number of attributes, and m is the logic block address. This is the total number of block addresses.

Each of the addresses of the feature matrix corresponds to the importance factor and contains a single-bit binary value indicating whether the attribute corresponding to one of the logical block addresses is significant.

The software component further includes determining a value of the single-bit binary value based on whether a threshold value corresponding to the attribute is satisfied.

The software component assigns the same stream ID to one of the logical block addresses having binary values that match at corresponding addresses in the feature matrix.

The software component determines, during each of the multiple timestamp windows, which stream group of the streams corresponds to the occurrence of concurrent data write requests, and determines the consistency attribute as one of the attributes for each of the logical block addresses. Evaluate the importance of

The software component evaluating the importance factor for the correspondence attribute indicates the logical block addresses of each of the streams of the stream group in an element in the queue for each of the timestamp windows, and the queue is filled. Case, comparing each element with all other elements, and identifying the logical block addresses of the streams of the stream group, respectively represented in each of the plurality of elements.

The software component further comprising generating a dictionary for allocating a stream ID to the next logical block address requests based on the importance factor for each of the attributes for each of the logical block address requests, and the memory Stores the dictionary.

According to another embodiment of the present invention, a method of identifying attributes respectively related to a logic block address corresponding to an input/output stream of data in a multi-streaming memory device includes: detecting an input/output stream corresponding to the memory device. Obtaining a plurality of attributes corresponding to the logic block address corresponding to the detected input/output stream, generating a feature matrix indicating importance coefficients of each of the attributes for the logic block address, and the Clustering the received data into different streams based on the feature matrix.

The method further includes generating an analysis model based on the feature matrix to evaluate aspects of clustering the received data into the different streams.

The method further includes the step of introducing a relative weighting factor for the analysis model by weighting the acquired attributes differently based on the importance level of each attribute.

The method further includes generating a dictionary based on the analysis model to assign a corresponding stream ID to the next received stream by performing a lookup.

Clustering the received data in different streams includes assigning a corresponding stream ID to the logical block address.

The plurality of attributes include frequency, temporal locality, sequentiality, or consistency.

Each address in the feature matrix includes a single-bit representing a significant coefficient corresponding to an attribute corresponding to the logical block address.

Clustering the received data into different streams includes determining which logical block addresses correspond to the received data.

Clustering the received data into different streams includes determining which logical block addresses are simultaneously accessed during each of a plurality of timestamp windows.

According to another embodiment of the present invention, a method of allocating an important coefficient of a correspondence attribute to a stream of data in a multi-stream memory device includes receiving streams of data respectively corresponding to logical block addresses (LBAs), Determining whether the number of unique logic block addresses accessed to each of a plurality of timestamp windows is less than a threshold value, inserting symbols corresponding to each of the timestamp windows, and the number of unique logic block addresses is greater than the threshold. Displaying each of the logical block addresses in a queue when not small, determining whether the inserted symbols are full in the queue, and which logic block during each of some of the timestamp windows when the queue is full And determining whether addresses are being accessed simultaneously.

The method further includes allocating the same stream ID to the streams corresponding to logical block addresses determined to be accessed simultaneously during each of some of the timestamp windows.

According to the present invention as described above, a multi-streaming flash drive is provided, in particular, it is possible to reduce write amplification and improve performance of solid state drives (SSDs).

Features of the invention will be understood and understood with reference to the detailed description, claims and accompanying drawings.
1 is a block diagram showing an analysis model for smart stream allocation with improved multi-threaded K-means clustering to consider multiple attributes according to an embodiment of the present invention.
2 is a sampling graph for explaining a novel consistency attribute according to an embodiment of the present invention.
3 is a flowchart of a matching attribute allocation according to an embodiment of the present invention.

The concept of the present invention and features of its implementation methods may be more easily understood with reference to the following embodiments and detailed description of the accompanying drawings. Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. However, the present invention may be embodied in various forms and should not be construed as being limited only to the embodiments shown here. Rather, these embodiments are provided by way of example so that this disclosure will be complete and complete, and will fully convey the aspects and features of the invention to those skilled in the art. Accordingly, processes, elements, and techniques unnecessary to those skilled in the art for a thorough understanding of aspects and features of the present invention may not be described. Unless otherwise stated, the same reference numerals refer to the same elements throughout the accompanying drawings and detailed description, and thus description thereof will not be repeated. In the drawings, the relative sizes of elements, layers, and regions may be exaggerated for clarity.

Terms such as “first”, “second”, “third” may be used herein to describe various elements, components, regions, layers, and/or sections, but these elements, configurations Elements, regions, layers and/or sections should not be limited by these terms. These terms are used to distinguish one element, component, region, layer and/or section from another element, component, region, layer and/or section. Accordingly, a first element, component, region, layer, or section described below may be referred to as a second element, component, region, layer or section without departing from the spirit and scope of the present invention.

Spatially relative terms such as "below", "lower", "lower", "lower", "above" "upper", etc. are, for convenience of description, in addition to the orientations shown in the drawings, one Spatially related terms may be used to describe the relationship between an element or feature and other element(s) or feature(s) shown in the drawings. For example, if the device in the figure is turned upside down, elements described as “below” or “bottom” or “bottom” for other elements or features face “up” for other elements or features. Will be Thus, exemplary terms of “below” and “below” may include both up and down directions. The device may be oriented in different directions (eg, may be rotated in 90 degrees or in other directions), and the spatially relative technical terminology used herein should be interpreted accordingly.

When an element, layer, region or component is referred to as “on”, “connected” or “coupled” to another element, layer, region or component, it is directly to the other component, layer, region or component. It may be connected, connected or combined, and there may be one or more intervening elements, layers, regions or components. In addition, when one element or layer is referred to as being “between” two elements or layers, there are only elements or layers between the two elements or layers, or one or more intervening elements or layers. May be.

The terms used in the present specification are intended to describe only specific embodiments and are not intended to limit the present invention. The singular form used in the present specification is intended to include the plural form unless otherwise indicated by context. As used herein, the terms "comprising" and "comprising" are specified features, integers, steps, actions, elements, and/or the presence of an element of one or more other features, It will be understood that the presence or addition of integers, steps, actions, elements, components and/or groups thereof is not excluded. As used herein, the term “and/or” includes any and all combinations of one or more related listed items. When an expression such as "at least one" precedes a list of elements, it modifies the entire list of elements and does not modify individual elements of the list.

The terms "substantially", "about" and similar terms used herein are used as terms of approximation, not as terms of degree, and describe the inherent deviation of a measured value or a calculated value. It is recognized by one of ordinary skill in the art to do so. Also, the use of "can" when describing an embodiment of the present invention means "one or more embodiments of the present invention." As used herein, the terms “use” and “used” may be considered synonymous with the terms “utilized” and “used”, respectively. Also, the term "exemplary" means a sample or illustration.

When a specific embodiment may be implemented differently, a specific processing order may be performed differently from the described order. For example, two consecutively described processes may be performed substantially simultaneously or may be performed in an order opposite to the described order.

The electronic or electrical device and/or any other related device or component according to the embodiments of the invention described herein may use any suitable hardware, firmware (e.g., custom integrated circuit), software, or combination of software. It can be implemented using For example, the various components of these devices may be formed on one integrated circuit (IC) chip or on individual IC chips. In addition, various components of these devices may be implemented on a flexible printed circuit film, a tape carrier package (TCP), a printed circuit board (PCB), or a single substrate. In addition, the various components of these devices run on one or more processors, run on one or more computing devices, execute computer program instructions, and interact with other system components to perform the various functions described herein. It may be a process or a thread. Computer program instructions are stored in memory that can be implemented in a computing device using standard memory devices such as random access memory (RAM), for example. Computer program instructions may also be stored on other non-transitory computer-readable media such as, for example, a CD-ROM, a flash drive, or the like. In addition, those skilled in the art are aware that functions of various computing devices may be combined or integrated into a single computing device, or functions of a specific computing device may be distributed through one or more other computing devices, without departing from the spirit and scope of the exemplary embodiments of the present invention. You will understand well that it can be.

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. In addition, terms such as definitions generally used in the dictionary should be interpreted as having a meaning consistent with the meaning in relation to the related technology and/or the present specification, and should not be interpreted as an ideal or excessively formal meaning.

As described above, efficient stream allocation in multi-streaming flash drives can reduce write amplification and improve lifespan, durability, and performance of SSDs. Streams of data can be more efficiently allocated by effectively synthesizing the benefits gained from different attributes, and by identifying and capturing attributes suitable for determining the corresponding stream ID.

Also, as described above, many existing multi-streaming systems take into account very few attributes of a particular entity (eg, frequency and temporal locality of accesses) for the purpose of automatic stream detection. The low performance improvements made by current automatic stream detection algorithms indicate that the new attributes of the identified streams may be suitable to reflect the life expectancy of data to be stored in multiple streams of SSDs.

Accordingly, embodiments of the present invention improve stream ID allocation for I/O requests under the application layer (eg, device driver, file system, etc.), and packetize I/O request traffic into multiple streams. To do this, we provide a new model for acquiring and including multiple attributes with a multi-streaming memory device. Unlike the conventional techniques, the described embodiments provide a scalable method capable of combining various attributes while providing a larger number of attributes considered for stream allocation, and thus the described embodiments provide a multi-streaming SSD You can better use their strengths. That is, the described embodiments can develop an analysis model for smart stream allocation with improved multi-threaded K-means clustering while considering multiple attributes. The described embodiments also enable the design of a low/minimum overhead training phase technique to obtain multiple attributes from an I/O trace, and also a new attribute called "congruency". Can explain the effect of consistency in efficient stream detection and identification.

Embodiments described below with respect to FIG. 1 are improved automation that can take into account multiple attributes such as frequency, temporal locality, sequentiality, and a new attribute "congruency". Stream allocation can be provided. The correspondence will be described in detail with reference to FIGS. 2 and 3.

FIG. 1 is a block diagram showing an analysis model for smart stream allocation using improved multi-threaded K-means clustering to consider multiple attributes according to an embodiment of the present invention. Although this embodiment is described as being placed in the device driver layer, and although the referenced entity of interest is a logical block address (LBA) corresponding to the incoming data, in other embodiments, the entity of interest is It may differ depending on the placement layer of the embodiments described for allocation. For example, the entity of interest may be replaced by a file for embodiments arranged in the file system layer.

Referring to FIG. 1, the analysis model of this embodiment is described as including two phases, which include a training phase 120 and a testing phase 130. In step S101 in the training step 120, the application platform may perform a training trace to obtain one or more appropriate attributes corresponding to the detected I/O streams for the SSD. These obtained attributes may include, for example, frequency, temporal locality, sequentiality and/or consistency. These attributes obtained from the training trace during step S101 will be described in more detail below.

Thereafter, in step S102, the obtained attributes may be used to extract features. Accordingly, it is possible to identify each of the extracted features for each of the detected I/O streams, and generate a feature matrix 140 that is used to indicate the significance level of each of the features.

The feature matrix 140 effectively represents the importance of the attribute when the importance of each extracted attribute (eg, an importance factor) corresponds to a logical block address (LBA) or a group of logical block addresses (LBAs). I can. Thus, the feature matrix 140 can be thought of as an nXm matrix with nXm entries. Here, n is the total number of attributes analyzed for stream detection and identification, and m is the total number of logic block addresses (LBAs).

The importance factor may be listed as data quanta stored in rows of feature matrix 140. Each entry in feature matrix 140 may be represented by a single binary bit indicating whether its attribute is considered important for a particular logical block address (LBA). For example, each address in feature matrix 140 may be "1" indicating that the attribute is important for its logical block address (LBA) or "1" indicating that the attribute is not important for that logical block address (LBA). May contain 0". That is, in order to obtain various properties (e.g., frequency, temporal locality, sequentiality, and consistency) with relatively low overhead, each property is a single-bit binary value for each LBA. ), but a multi-bit value may be used to indicate the level of importance (eg, degrees of change in importance) for each LBA. The binary value for the LBA entry is 0 when the attribute of the feature matrix 140 is less than or not equal to the corresponding element of the threshold vector, and 1 otherwise. The threshold vector can be thought of as an nX1 matrix with nX1 entries. Where n is the total number of attributes, and each entry in this matrix corresponds to the threshold of each attribute. How each of the individual attributes is obtained is described separately below.

The feature matrix 140 may be used, for example, to cluster data writes corresponding to different logical block addresses (LBAs) in different streams. Therefore, the improved multi-threaded K-means method can be used as a clustering model for clustering or grouping data writes to different streams, and K-means is an iterative autonomous clustering application. . Each of the acquired attributes may constitute a feature of data clustering. That is, each of the acquired attributes used to identify various types of data by the characteristics of the acquired attributes may correspond to one row or one column of the feature matrix 140.

When the feature matrix 140 is generated, in step S103, an analysis model for detecting and identifying different I/O streams may be initialized. The initialization model represents the K-means clustering.

Accordingly, in step S104, the initialized model is trained to generate a model 160 for evaluation, and then in step S105, the model 160 is evaluated. Model 160 may effectively shape itself or train itself using machine-learning or self-learning algorithms. This may allow the model 160 to effectively emphasize that certain attributes are more important than others in determining the stream IDs to allocate different LBAs.

The relative weight factor corresponding to each of the different attributes may be basically unity. However, in step S106, an optional relative weighting factor may be introduced into the model 160. That is, all of the acquired attributes may be initially weighted equally, but in step S106, in order to emphasize the relative importance of each attribute when determining and assigning a corresponding stream ID, a relative weighting coefficient matrix corresponding to the attributes May be tuned to the generated model 160 and transmitted as an optional input. For example, if one of the extracted attributes has a relatively higher importance level than the other extracted attributes, a higher weighting factor can be assigned to that attribute by introducing a relative weighting factor into the model 160 , It may be evaluated or re-evaluated in step S105 (eg, to be adjusted to comply with specifications determined by the user or system).

At the end of the training step 120, if clustering is performed during a relatively small number of iterations (e.g., 4 or 5 iterations) in step S104, step S105, and optionally step S106, in step S107 , A dictionary 150 is formed to express the relationship of each of the LBAs (for example) to the corresponding stream ID, so that the stream IDs can be automatically assigned to new data based on the identified corresponding LBA. have. In other embodiments, the training step 120 may be performed as an initial step in the method, and/or periodically during the test step 130 to adjust the dictionary to compensate for any workload changes. Can be done. The dictionary 150 may be stored on a disk in memory, and may be stored in, for example, a device layer, a block layer, or an application layer so that the dictionary 150 can be used during the execution time of the test step 130.

Thus, during the test step 130, in step S108, new data is entered to be written to the memory with the running workload. Thereafter, in step S109, a lookup may be performed using the dictionary 150. That is, when new data comes in in step S108, the LBA corresponding to the new data received in step S108 can be identified, and, based on the lookup of the dictionary 150 generated during the training step 120, the stream ID Is allocated based on the LBA corresponding to the newly received data, so that related data can be grouped accordingly.

Thereafter, in step S110, a corresponding physical address may be assigned to the stream ID. That is, while running the workload, a quick lookup to dictionary 150 is only needed for stream ID assignment without any runtime measurement overhead. Therefore, the test step 130 can be performed relatively quickly without additional overhead.

It should be noted that the above-described analytic model can be placed in any layer (eg, file system, device driver, etc.), thus eliminating any need for applications to be involved in the process of allocating stream IDs. Also, for each I/O operation and depending on the implementation layer, the analytic model knows the logic block numbers or files that are requested to be written to the SSD, so that the self-learning model takes trends in accessing those logic block numbers or files. Allow to find.

It should also be noted that the analysis model described above is flexible over a number of overall properties that can be evaluated. Thus, the analytic model can be used to determine any number of stream IDs taking into account any number of attributes. Thus, the invention is not limited to a specific number of attributes or a specific number of streams. For example, embodiments of the present invention can support future technologies in this field even if the number of streams supported by multi-stream flash drives is changed.

Examples of methods for obtaining various attributes, as performed by the training trace in step S101, are described below.

The attribute of frequency may correspond to how often a particular address was attempted to be accessed as a result of data entry. In order to obtain the attribute of the frequency, if the number of accesses of any particular address is less than a preset threshold (e.g. 4 times), the frequency attribute corresponding to that particular address can be assigned as 1 representing the importance, otherwise Otherwise, it can be assigned to zero.

The attribute of temporal locality may correspond to how recently a particular address was attempted to be accessed. In order to obtain the property of temporal locality, a maximum timestamp of the training trace can be determined, and addresses accessed after a preset threshold of the maximum timestamp (e.g., 50%) are temporal locality. It can be marked as recent by assigning 1 to the property, otherwise assigning the temporal property to 0.

The attribute of sequentiality may correspond to whether or not the data input attempts to access specific addresses in a sequential order. In order to obtain the nature of the sequence, when a new I/O stream is received by the sequence detector, the sequence detector looks for the previous (or some predefined window size, e.g. 16) LBA in a given trace. up) you can. If a match is found, the sequentiality attribute is assigned 1, otherwise it can be assigned 0.

2 is a sampling graph illustrating a novel congruency attribute according to an embodiment of the present invention.

The attribute of consistency, an attribute introduced by embodiments of the present invention, corresponds when entities of different interests, such as LBAs, are updated regularly or almost simultaneously. For example, if the addresses of a particular group are updated frequently or almost always, at about the same time, it can be said that the groups of such LBAs match each other. Since matching addresses are accessed simultaneously, it may be useful to group them together to improve the performance of the memory device.

In Fig. 2, the x-axis of the sampling graph corresponds to a timestamp (eg, a timestamp window or time interval), and the y-axis corresponds to the LBA space. In this embodiment, consistency can be considered as the quality of one or more LBAs consistently timed with one or more other LBAs. Thus, if a specific group of LBAs is frequently updated almost at the same time, the group of LBAs can be said to match each other. Thus, in the example shown in Fig. 2, LBA2 and LBA3 coincide with each other because they are all updated simultaneously in three of the four timestamp windows/time intervals indicated by vertical dotted lines. In order to obtain the attribute of consistency with low overhead, a fixed length queue can be maintained, where each element or slot of the queue represents an observed time interval/timestamp window. .

More specifically, the device of an embodiment of the present invention may "snoop" between or at specific time intervals. In the example shown in Fig. 2, instances of snoop are indicated by vertical dashed lines. It can be seen that LBA2 and LBA3 are updated coincidently at the first snoop time 210. Similarly, FIG. 2 shows that LBA2 and LBA3 are accessed simultaneously at the second snoop time 220 and the third snoop time 230. Since different snoop times indicate that LBA2 and LBA3 tend to be updated simultaneously (e.g., congruent), LBA2 and LBA3 may have similar life cycles, so LBA2 and LBA3 can be combined in a single stream. Grouping them together can be beneficial.

3 is a flow chart of concordance attribute assignment according to an embodiment of the present invention.

Referring to FIG. 3, in the process of obtaining the consistency attribute, a process of determining the correspondence attribute using exemplary symbols [-, x, o, |, +] to indicate unique LBA addresses. A flowchart of is shown. The queue 300 includes a number of elements or slots, and each element of the queue 300 is accessed within a corresponding timestamp window corresponding to an element (each element of the queue 300 referring to a single timestamp window). It keeps a list of all the unique LBAs.

In step S301, it is determined whether the number of unique LBAs is smaller than a given threshold value (eg, threshold value "β"). Each timestamp window will correspond to all LBAs accessed within that timestamp window, and the decision to insert a particular timestamp window into queue 300 depends on the number of all unique LBAs accessed within that timestamp window. , LBAs can be represented by various symbols. For example, in this embodiment, in the first timestamp window 310, the "-" LBA has been accessed, and in the second timestamp window 320, "x" LBA and "|" LBAs were accessed together, and in the third timestamp window 330 "-" LBA, "x" LBA, "|" LBA and “+” LBA were accessed together, and “-” LBA and “o” LBA were accessed together in the fourth timestamp window 340.

Logically, a small number of LBAs within a given timestamp window are accessed, but when the combination of such small number of LBAs matches (i.e. they are accessed multiple times and also accessed simultaneously for multiple such multiple times), such LBAs The importance of grouping them into the same stream may be appropriate. Thus, once the trace is achieved (eg, as described in FIG. 1), the input can be analyzed.

In step S301, if it is determined that the unique LBAs accessed in the timestamp window are smaller than a predetermined threshold value, in step S302, a specific timestamp window is inserted into the queue 300. However, if the unique LBAs accessed in the timestamp window in step S301 are not smaller than the given threshold, in step S303, the process moves to the next timestamp window. It may be advantageous to ignore the timestamp window with a relatively large number of accessed LBAs, as a large number may indicate a lower importance for consistency. Therefore, by not bringing timestamp windows having a relatively large number of addresses to the queue 300, the calculation can be performed faster, and the training step 120 described in FIG. 1 can be more efficient.

In step S304, it is determined whether the queue 300 is full. Once the length of the queue 300 is filled, in step S305, a dequeue is triggered by appending a value to the consistency attribute. The length of the queue 300 can be adjusted.

During dequeue, each timestamp window is compared to all other timestamp windows to identify matching elements. When it is determined during the DQ operation that the subset values of the first element list of the queue 300 match the subset values of the other element list of the queue 300, the values of the subsets are displayed as 1 (for example, , Congruent). If the values of a subset of the element list do not match values of a subset of any other element list, the values of the subset corresponding to that element are marked as 0 (eg, not congruent). The threshold of the size of the subset for determining the correspondence can be adjusted, for example, can be set to three values, and of two different elements with matching subsets containing only two matching values. Lists can still be marked as 0 (ie, mismatch). In step S305, the D-Q is operated in FIFO (first in first out) order.

In step S306, a matrix (e.g., a correspondence matrix) is generated by assigning a single-bit binary value to each of the symbols representing LBAs. "x" LBA and "|" Since the LBA is accessed both in the second and third timestamp windows 320 and 330 and not in another timestamp window, the "x" LBA and "|" All LBAs are determined to be congruent and assigned a value of “1”, and the remaining LBAs are determined to be non-congruent and assigned a value of “0”.

Also in other implementations, since there may be various sub-attributes, there may be multiple columns in the consistency matrix of step S306, and each row of the correspondence matrix may reference data from different attributes.

Thereafter, once the consistency matrix is generated in step S306, the dictionary 150 generated during the training step 120 of FIG. 2 is used as a lookup table for allocating stream IDs to streams of various data.

Accordingly, the embodiments of the present invention described above can be implemented without the need of any application level changes, and thus can be used for any application, workload or platform used to run multiple applications simultaneously, and can also The use of properties of can be made possible. Moreover, different attributes can be added, removed or even tuned using the appropriate relative weighting factors described above, thus enabling high quality Stream ID packetization.

Also, since only a single hard lookup in dictionary 150 is used during test step 130, metrology overhead is low/minimized, thus speeding up the processes of the described embodiments during testing. In addition, since the embodiments can be applied to different contexts, the important is separated from the non-critical, and the described embodiments are used for high temperature, room temperature and low temperature data identification problems, multi-tiered storage , It can be applied to various fields such as efficient caching.

The above description is for describing exemplary embodiments and should not be construed as limiting the present invention. Although several exemplary embodiments have been described, those skilled in the art will readily appreciate that many variations are possible in the exemplary embodiments without substantially departing from the novel teachings and effects of the exemplary embodiments. Accordingly, all such modifications are intended to be included within the scope of the exemplary embodiments defined in the claims. In the claims, the terms mean-plus-function are intended to encompass the structure described herein by listing structural equivalents as well as equivalent structures. Accordingly, the above-described embodiments are for describing exemplary embodiments, and should not be construed as being limited to the specific disclosed embodiments, and within the scope of the appended claims, the disclosed exemplary embodiments and other exemplary embodiments It should be understood to include variations on the examples. The concept of the invention is defined by the following claims and includes equivalents of the scope of the claims.

140: feature matrix
150: dictionary 160: model

Claims (10)

For a multi-streaming memory system:
Memory; And
Including a processor connected to the memory,
The processor running a software component that improves stream allocation in multi-streaming flash drives comprises:
Identify attributes each associated with the logical block addresses, each corresponding to each of the plurality of streams of data writes, and each representing an expected life of data stored in the corresponding stream;
In order to evaluate the importance coefficient of any one of the attributes indicating the likelihood that the group of logical block addresses will be accessed with any one of the attributes for each of the streams, any one of the streams Determine whether to respond to simultaneous data write requests occurring in each of the timestamp windows,
The above is to determine:
Indicating the logical block addresses of each of the streams of the stream group in an element in the queue for each of the timestamp windows;
Comparing each of the elements with all other elements; And
Performed by identifying the logical block addresses of the streams of the stream group each represented within each of a plurality of the elements, and
Two or more clustered logic, based on each of the logical block addresses and all importance coefficients for a stream to which a stream ID is assigned, and an indication that the expected lifetime of the data of two or more logical block addresses will be similar. Clustering two or more of the logical block addresses into one or more data write streams by assigning a single stream ID to each of the block addresses; And
A multi-streaming memory system for writing the data in the streams of data writes. The method of claim 1,
The software component further comprises assigning a weighting factor to one or more of the attributes, and
The software component assigns the stream ID to each of the logical block addresses by giving priority to importance coefficients corresponding to the attributes over other importance coefficients based on the assigned weighting coefficient. system. The method of claim 1,
The software component evaluates the importance coefficient for each of the attributes for each of the logical block addresses by generating an n × m feature matrix comprising n × m addresses, wherein n is the total number of the attributes, And m is the total number of the logical block addresses. The method of claim 3,
Each of the addresses of the feature matrix corresponds to the importance factor and includes a single-bit binary value indicating whether an attribute corresponding to any of the logical block addresses is significant. The method of claim 4,
The software component further comprising determining a value of the single-bit binary value based on whether a threshold value corresponding to a corresponding one of the attributes is satisfied. The method of claim 5,
And the software component allocating the same stream ID to logical block addresses having binary values that match at corresponding ones of the addresses of the feature matrix among the logical block addresses. The method of claim 1,
The software component further comprises generating a dictionary for assigning a stream ID to the future logical block address requests based on the importance factor for each of the attributes for each of the logical block address requests, and
The memory is a multi-streaming memory system for storing the dictionary. A method of identifying attributes respectively related to a logical block address corresponding to an input/output stream of data in a multi-streaming memory device for improving stream allocation in multi-streaming flash drives:
Detecting an input/output stream corresponding to the multi-streaming memory device;
Acquiring a plurality of attributes corresponding to a logic block address corresponding to the detected input/output stream, and indicating an expected lifetime of data to be stored in the detected input/output stream;
Generating a feature matrix representing importance coefficients of each of the attributes related to the logical block address;
To evaluate the importance factor of any one of the attributes indicating the likelihood that the group of logical block addresses will be accessed with any of the attributes for each of the streams, during each of a plurality of timestamp windows, the Determining which stream group among the streams corresponds to simultaneous data write requests;
Based on the feature matrix and an indication that the expected lifetime of the data of two or more of the logical block addresses is similar, the received data corresponding to the two or more of the logical block addresses is transferred to one or more streams of different data writes Clustering on; And
Writing the data of the streams of the data writes,
The determining step is:
Indicating logical block addresses of each of the streams of the stream group in an element in a queue for each of the timestamp windows;
Comparing each of the elements with all other elements; And
And identifying the logical block addresses of the streams of the stream group each represented in each of a plurality of the elements. The method of claim 8,
And generating an analysis model based on the feature matrix to evaluate the clustering of the received data in the different streams. A method of allocating an attribute importance factor to a stream of data in a multi-stream memory device for improving stream allocation in multi-streaming flash drives is:
Receiving the streams of data respectively corresponding to logical block addresses;
Determining whether the number of unique logical block addresses accessed to each of the plurality of timestamp windows is less than a threshold value;
Inserting symbols respectively corresponding to the timestamp windows and representing each of the logical block addresses into a queue when the number of unique logical block addresses corresponding to the queue is not less than the threshold value;
Determining whether the inserted symbols are full in the queue;
Determining which of the logical block addresses are simultaneously accessed during each of a plurality of timestamp windows among the timestamp windows when the queue is full; And
And writing the data of the streams of data.

Images