SH>>И получаем бинарное дерево, о котором говорил теоретик Правда, без указателей, но тем не менее.

heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B)

SH>>>И получаем бинарное дерево, о котором говорил теоретик Правда, без указателей, но тем не менее.

R>

If the tree root item has index 0 (n tree elements are a[0] .. a[n−1]), then for each index i, element a[i] has children a[2i+1] and a[2i+2], and the parent a[floor((i−1)/2)]

Большие матрицы, например, текстуры в видеопамяти, хранятся кусочками типа 16x16.

Текстуры в видеопамяти хранятся кусочками типа 16x16.

R>>Вроде ж как при модификации кода модификация будет распространяться по протоколу когерентности на общих основаниях

7.1.3 Handling Self- and Cross-Modifying Code
The act of a processor writing data into a currently executing code segment with
the intent of executing that data as code is called self-modifying code. IA-32
processors exhibit model-specific behavior when executing self-modified code,
depending upon how far ahead of the current execution pointer the code has been
modified.
As processor microarchitectures become more complex and start to speculatively
execute code ahead of the retirement point (as in P6 and more recent processor
families), the rules regarding which code should execute, pre- or post-modification,
become blurred. To write self-modifying code and ensure that it is compliant with
current and future versions of the IA-32 architectures, use one of the following
coding options:
(* OPTION 1 *)
Store modified code (as data) into code segment;
Jump to new code or an intermediate location;
Execute new code;
(* OPTION 2 *)
Store modified code (as data) into code segment;
Execute a serializing instruction; (* For example, CPUID instruction *)
Execute new code;
The use of one of these options is not required for programs intended to run on the
Pentium or Intel486 processors, but are recommended to insure compatibility with
the P6 and more recent processor families.
Self-modifying code will execute at a lower level of performance than non-self-modifying
or normal code. The degree of the performance deterioration will depend upon
the frequency of modification and specific characteristics of the code.
The act of one processor writing data into the currently executing code segment of a
second processor with the intent of having the second processor execute that data as
code is called cross-modifying code. As with self-modifying code, IA-32 processors
exhibit model-specific behavior when executing cross-modifying code, depending
upon how far ahead of the executing processors current execution pointer the code
has been modified.
To write cross-modifying code and insure that it is compliant with current and future
versions of the IA-32 architecture, the following processor synchronization algorithm
must be implemented:
(* Action of Modifying Processor *)
Memory_Flag ← 0; (* Set Memory_Flag to value other than 1 *)
Store modified code (as data) into code segment;
Memory_Flag ← 1;
(* Action of Executing Processor *)
WHILE (Memory_Flag ≠ 1)
Wait for code to update;
ELIHW;
Execute serializing instruction; (* For example, CPUID instruction *)
Begin executing modified code;
(The use of this option is not required for programs intended to run on the Intel486
processor, but is recommended to insure compatibility with the Pentium 4, Intel
Xeon, P6 family, and Pentium processors.)
Like self-modifying code, cross-modifying code will execute at a lower level of performance
than non-cross-modifying (normal) code, depending upon the frequency of
modification and specific characteristics of the code.
The restrictions on self-modifying code and cross-modifying code also apply to the
Intel 64 architecture.

10.6 SELF-MODIFYING CODE
A write to a memory location in a code segment that is currently cached in the
processor causes the associated cache line (or lines) to be invalidated. This check is
based on the physical address of the instruction. In addition, the P6 family and
Pentium processors check whether a write to a code segment may modify an instruction
that has been prefetched for execution. If the write affects a prefetched instruction,
the prefetch queue is invalidated. This latter check is based on the linear
address of the instruction. For the Pentium 4 and Intel Xeon processors, a write or a
snoop of an instruction in a code segment, where the target instruction is already
decoded and resident in the trace cache, invalidates the entire trace cache. The latter
behavior means that programs that self-modify code can cause severe degradation
of performance when run on the Pentium 4 and Intel Xeon processors.
In practice, the check on linear addresses should not create compatibility problems
among IA-32 processors. Applications that include self-modifying code use the same
linear address for modifying and fetching the instruction. Systems software, such as
a debugger, that might possibly modify an instruction using a different linear address
than that used to fetch the instruction, will execute a serializing operation, such as a
CPUID instruction, before the modified instruction is executed, which will automatically
resynchronize the instruction cache and prefetch queue. (See Section 7.1.3,
“Handling Self- and Cross-Modifying Code,” for more information about the use of
self-modifying code.)
For Intel486 processors, a write to an instruction in the cache will modify it in both
the cache and memory, but if the instruction was prefetched before the write, the old
version of the instruction could be the one executed. To prevent the old instruction
from being executed, flush the instruction prefetch unit by coding a jump instruction
immediately after any write that modifies an instruction.

10.4 CACHE CONTROL PROTOCOL
The L1 instruction cache in P6 family processors implements only the “SI” part of the
MESI protocol, because the instruction cache is not writable. The instruction cache
monitors changes in the data cache to maintain consistency between the caches
when instructions are modified. See Section 10.6, “Self-Modifying Code,” for more
information on the implications of caching instructions.

17.28.1 Self-Modifying Code with Cache Enabled
On the Intel486 processor, a write to an instruction in the cache will modify it in both
the cache and memory. If the instruction was prefetched before the write, however,
the old version of the instruction could be the one executed. To prevent this problem,
it is necessary to flush the instruction prefetch unit of the Intel486 processor by
coding a jump instruction immediately after any write that modifies an instruction.
The P6 family and Pentium processors, however, check whether a write may modify
an instruction that has been prefetched for execution. This check is based on the
linear address of the instruction. If the linear address of an instruction is found to be
present in the prefetch queue, the P6 family and Pentium processors flush the
prefetch queue, eliminating the need to code a jump instruction after any writes that
modify an instruction.

Cache-Conscious Design

Locality is a first-order issue that trumps much of our existing understanding of performance optimization. Most traditional optimization techniques come after "locality" on parallel hardware (although a few are still equally or more important than locality, such as big-Oh algorithmic complexity for example).

Arrange your data carefully by following these three guidelines, starting with the most important:

First: Keep data that are not used together apart in memory. If variables A and B are not protected by the same mutex and are liable to be used by two different threads, keep them on separate cache lines. (Add padding, if necessary; it's a great way to "waste" memory to make your code run faster.) This avoids the invisible convoying of false sharing (ping-pong) where in the worst case only one contending thread can make progress at all, and so typically trumps other important cache considerations.

Second: Keep data that is frequently used together close together in memory. If a thread that uses variable A frequently also needs variable B, try to put A and B in the same cache line if possible. For example, A and B might be two fields in the same object that are frequently used together. This is a traditional technique to improve memory performance in both sequential and concurrent code, which now comes second to keeping separate data apart.

Third: Keep "hot" (frequently accessed) and "cold" (infrequently accessed) data apart. This is true even if the data is conceptually in the same logical object. This helps both to fit "hot" data into the fewest possible cache lines and memory pages and to avoid needlessly loading the "colder" parts. Together these effects reduce (a) the cache footprint and cache misses, and (b) the memory footprint and virtual memory paging.

The constant-access-time “flat” memory illusion is as important as the serial illusion. In a flat memory, every location in memory can be accessed with exactly the same cost, independent of the order of access. For decades, this simple cost model has been used as an implicit assumption in the design of computer programs. Even theoretical computer science, which analyzes the best-case asymptotic complexity of algorithms for solving various abstract problems, is primarily based on this illusion. Unfortunately, it is just an illusion, although computer architects have been able to develop many clever mechanisms to maintain it. However, the latency of accessing a random word in external main memory (DRAM) is quite slow compared to processor speed, by two orders of magnitude or more. A computer using a memory system consisting only of DRAM would be intolerably slow, so modern machines instead have a memory hierarchy, where copies of certain parts of the memory space are kept in faster, smaller cache memories. If the most frequently accessed data can be kept in the fastest cache memories, then on average a low access cost can be achieved. The memory hierarchy exploits the fact that typical programs exhibit spatial and temporal locality. This mechanism has been reasonably successful at maintaining the flat memory illusion in serial computers. However, even in serial computers significant performance gains are possible by designing programs using a more realistic memory model. For example, it is worthwhile to use data structures and algorithms that are designed to have high levels of spatial and temporal locality.

R>