Đang chuẩn bị liên kết để tải về tài liệu:
THE FRACTAL STRUCTURE OF DATA REFERENCE- P12

THE FRACTAL STRUCTURE OF DATA REFERENCE- P12:For purposes of understanding its performance, a computer system is traditionally viewed as a processor coupled to one or more disk storage devices, and driven by externally generated requests (typically called transactions). Over the past several decades, very powerful techniques have become available to the performance analyst attempting to understand, at a high level, the operational behavior of such systems. | Hierarchical Reuse Daemon 4 1 Figure 2.2. Distribution of interarrival times for a synthetic application running at one request per second with v 0.40 corresponding to 0 0.25 . Figure 2.3. Distribution of interarrival times for a synthetic application running at one request per second with v 0.34 corresponding to 0 0.35 . 42 THE FRACTAL STRUCTURE OF DATA REFERENCE A general-purpose technique exists for generating synthetic patterns of reference which is also capable of producing references that conform to the hierarchical reuse model. This technique is based upon the concept of stack distance or the depth at which previously referenced data items appear in the lru list 8 21 . The idea is to build a history of previous references organized in the form of an lru list and index into it using a random pointer that obeys a specified probability distribution. Due to the ability to manipulate the probability distribution ofpointer values this technique has much greater generality than the toy application proposed in the present chapter. The memory and processing requirements implied by maintaining a large randomly accessed lru list of previous references however make this approach problematic in a real-time benchmark driver. In the same paper ofhis just referenced in the previous paragraph Thiebaut also touches upon the possibility ofproducing synthetic references by performing a random walk 21 . The form that he suggests for the random walk is based upon the fractal relationships among successive reference locations as observed by himself and others. It is not clear from the material presented in the paper however whether or not Thiebaut actually attempted to apply this idea or what results he might have obtained. Returning to the context ofthe hierarchical reuse model we have shown that its behavior can in fact be produced by a specific form of random walk. The proposed random walk technique has the important advantage that there is no need to maintain a reference .