在基于fork的多进程实现中，每次fork会让子进程得到不同的虚拟空间地址，但此时其映射的还是父进程的物理内存空间，可以让子进程高效率读取父进程的memory数据。一旦子进程有写操作就会触发操作系统的copy-on-write异常，系统会拷贝出另一块空间供子进程使用。

Once a compiler must resort to register spilling, any advantage of maintainingmultiple accumulators will most likely be lost.

a reassociation transformation can reduce the number of opera-tions along the critical path in a computation, resulting in better performance bybetter utilizing the multiple functional units and their pipelining capabilities.

Loop unrolling can improve performance in two ways. First,it reduces the number of operations that do not contribute directly to the programresult, such as loop indexing and conditional branching. Second, it exposes waysin which we can further transform the code to reduce the number of operationsin the critical paths of the overall computation.

For an operation with latency L and capacity C, thisrequires an unrolling factor k ≥ C

are evaluated simultaneously, a phenomenon referred to as instruction-level paral-lelism.

If a compiler cannotdetermine whether or not two pointers may be aliased, it must assume that eithercase is possible, limiting the set of possible optimizations.

The case where two pointers may designate the same memory location isknown as memory aliasing.

Focus your attention on the inner loops, where the bulk of the computationsand memory accesses occur.. Try to maximize the spatial locality in your programs by reading data objectssequentially, with stride 1, in the order they are stored in memory.. Try to maximize the temporal locality in your programs by using a data objectas often as possible once it has been read from memory.

Repeated references to local variables are good because the compiler cancache them in the register file (temporal locality).. Stride-1 reference patterns are good because caches at all levels of the memoryhierarchy store data as contiguous blocks (spatial locality).

we suggest adopting a mental model that assumeswrite-back, write-allocate caches.

fully associative caches are only appropriate for small caches

A copy of w is contained in the line if and only if the valid bit is setand the tag in the cache line matches the tag in the address of w.

The process that a cache goes through of determining whether a request is ahit or a miss and then extracting the requested word consists of three steps: (1) setselection, (2) line matching, and (3) word extraction.

std::shared_ptr can be used when you need multiple smart pointers that can co-own a resource. The resource will be deallocated when the last std::shared_ptr goes out of scope. std::weak_ptr can be used when you want a smart pointer that can see and use a shared resource, but does not participate in the ownership of that resource.

Always make a copy of an existing std::shared_ptr if you need more than one std::shared_ptr pointing to the same resource.

Redistribution can easily become a bottleneck due to the bandwidthof cross-device links usually being magnitudes smaller than that of the on-device memory bus.

Modern large-scale deep learning workloads highlight the need for parallel execution across many devicesin order to fit model data into hardware accelerator memories. In these settings, array redistribution maybe required during a computation, but can also become a bottleneck if not done efficiently

Second, don’t manually delete the resource out from underneath the std::unique_ptr.

Use std::make_unique() instead of creating std::unique_ptr and using new yourself.

Favor std::array, std::vector, or std::string over a smart pointer managing a fixed array, dynamic array, or C-style string.

Because std::unique_ptr is designed with move semantics in mind, copy initialization and copy assignment are disabled. If you want to transfer the contents managed by std::unique_ptr, you must use move semantics.

std::move_if_noexcept will return a movable r-value if the object has a noexcept move constructor, otherwise it will return a copyable l-value. We can use the noexcept specifier in conjunction with std::move_if_noexcept to use move semantics only when a strong exception guarantee exists (and use copy semantics otherwise).

std::move can be used whenever we want to treat an l-value like an r-value for the purpose of invoking move semantics instead of copy semantics.

the goal of the move constructor and move assignment is to move ownership of the resources from one object to another (which is typically much less expensive than making a copy).

By default, C++ will provide a copy constructor and copy assignment operator if one is not explicitly provided. These compiler-provided functions do shallow copies, which may cause problems for classes that allocate dynamic memory. So classes that deal with dynamic memory should override these functions to do deep copies.

First, r-value references extend the lifespan of the object they are initialized with to the lifespan of the r-value reference (l-value references to const objects can do this too). Second, non-const r-value references allow you to modify the r-value!

Move semantics means the class will transfer ownership of the object rather than making a copy.

A Smart pointer is a composition class that is designed to manage dynamically allocated memory and ensure that memory gets deleted when the smart pointer object goes out of scope.

1. Multiple strong symbols are not allowed○ Each item can be defined only once2. Given a strong symbol and multiple weak symbols, choose the strong symbol○ References to the weak symbol resolve to the strong symbol3. If there are multiple weak symbols, pick an arbitrary one

● Relocatable object file (.o file)○ Code and data that can be combined with other relocatable object files to form executable object file■ Each .o file is produced from exactly one source (.c) file● Executable object file (a.out file)○ Code and data that can be copied directly into memory and then executed● Shared object file (.so file)○ Special type of relocatable object file that can be loaded into memory and linked dynamically, at either load time or run-time

● Static Linking○ Executable files and running memory images contain only the library code they actually use● Dynamic linking○ Executable files contain no library code○ During execution, single copy of library code can be shared across all executing processes

● Modularity○ Program can be written as a collection of smaller source files, rather than one monolithic mass.● Efficiency○ Time: Separate compilation■ Change one source file, compile, and then relink. No need to recompile other source files.○ Space: Libraries■ Common functions can be aggregated into a single file...

● Global symbols○ Symbols defined by module m that can be referenced by other modules.■ e.g., non-static C functions and non-static global variables.● External symbols○ Global symbols that are referenced by module m but defined by some other module.● Local symbols○ Symbols that are defined and referenced exclusively by module m.■ e.g., C functions and global variables defined with the static attribute.○ Local linker symbols are not local program variables

● Symbol resolution○ Programs define and reference symbols (global variables and functions)○ Linker associates each symbol reference with exactly 1 symbol definition● Relocation○ Merges separate code and data sections into single sections○ Relocates symbols from relative locations in .o files to final memory locations○ Updates all references to symbols to reflect new positions

● Aggregates multiple independently compiled files containing machine code● Fills in those unknown addresses● The goal is to create 1 file with all of the needed code to run the program

○ This changes the format and structure of the code but preserves the semantics (what it does)○ Can change lots of details for optimization, as long as the overall effect is the same

● Processes #include, #define, #if, macros○ Combines main source file with headers (textually)○ Defines and expands macros (token-based shorthand)○ Conditionally removes parts of the code (e.g. specialize for Linux, Mac, ...)● Removes all comments

Four steps for C: preprocessing, compiling, assembling, linking

Restrictive placement policies of this kind lead to a type of miss known asa conflict miss, in which the cache is large enough to hold the referenced dataobjects, but because they map to the same cache block, the cache keeps missing.

When the size of the working set exceedsthe size of the cache, the cache will experience what are known as capacity misses.

For caches high in the memory hierarchy (close tothe CPU) that are implemented in hardware and where speed is at a premium,this policy is usually too expensive to implement because randomly placed blocksare expensive to locate.

The decision about which block to replace is governed by the cache’s replacementpolicy.

a program needs a particular data object d from level k + 1, it first looksfor d in one of the blocks currently stored at level k. If d happens to be cachedat level k, then we have what is called a cache hit.

It is important to realize that while the block size is fixedbetween any particular pair of adjacent levels in the hierarchy, other pairs of levelscan have different block sizes.

The central idea of a memory hierarchy is that for each k, the faster and smallerstorage device at level k serves as a cache for the larger and slower storage device

Programs that repeatedly reference the same variables enjoy good temporallocality..For programs with stride-k reference patterns, the smaller the stride, thebetter the spatial locality. Programs with stride-1 reference patterns have goodspatial locality. Programs that hop around memory with large strides havepoor spatial locality..Loops have good temporal and spatial locality with respect to instructionfetches. The smaller the loop body and the greater the number of loop it-erations, the better the locality.

Visiting every kth element of a contiguous vector is called a stride-kreference pattern. Stride-1 reference patterns are a common and important sourceof spatial locality in programs. In general, as the stride increases, the spatial localitydecreases.

Their alignment rule is based on the principle that any primitiveobject of K bytes must have an address that is a multiple of K.

The disadvantage of the two-dimensional array organization isthat addresses must be sent in two distinct steps, which increases the access time.

One reason circuit designers organize DRAMs as two-dimensional arraysinstead of linear arrays is to reduce the number of address pins on the chip.

The memory system must periodically refresh every bit of memory byreading it out and then rewriting it.

初始大小以宏 LEPT_PARSE_STACK_INIT_SIZE 的形式定义，使用 #ifndef X #define X ... #endif 方式的好处是，使用者可在编译选项中自行设置宏，没设置的话就用缺省值。

The %rip register on x86-64 is a special-purpose register that always holds the memory address of the next instruction to execute in the program's code segment.

• %rax: return value• %rsp: stack pointer• %rdi: 1st argument• %rsi: 2nd argument• %rdx: 3rd argument• %rcx: 4th argument• %r8: 5th argument• %r9: 6th argument

To manage a variable-size stack frame, x86-64 code uses register %rbp to serveas a frame pointer

The techniques we have outlined—randomization, stack protection, and lim-iting which portions of memory can hold executable code—are three of the mostcommon mechanisms used to minimize the vulnerability of programs to bufferoverflow attacks

The array elements areordered in memory in row-major order, meaning all elements of row 0, whichcan be written A[0], followed by all elements of row 1 (A[1]), and so on.

The final example shows that one cancompute the difference of two pointers within the same data structure, with theresult being data having type long and value equal to the difference of the twoaddresses divided by the size of the data type.

if p is a pointer to dataof type T , and the value of p is xp, then the expression p+i has value xp + L . i,where L is the size of data type T

convention, registers %rbx, %rbp, and %r12–%r15 are classified as callee-saved registers. When procedure P calls procedure Q, Q must preserve the valuesof these registers, ensuring that they have the same values when Q returns to P asthey did when Q was called

At times, however, local data mustbe stored in memory. Common cases of this include these:.There are not enough registers to hold all of the local data..The address operator ‘&’ is applied to a local variable, and hence we must beable to generate an address for it..Some of the local variables are arrays or structures and hence must be accessedby array or structure references.

When an x86-64 procedure requires storage beyond what it can hold in reg-isters, it allocates space on the stack. This region is referred to as the procedure’s

The advantage of usinga jump table over a long sequence of if-else statements is that the time taken toperform the switch is independent of the number of switch cases.

If one of those two expressions couldpossibly generate an error condition or a side effect, this could lead to invalidbehavior. Such is the case for our earlier example

The testinstructions behave in the same manner as the and instructions, except that theyset the condition codes without altering their destinations.

The cmp instructions set the condition codes according to the differences of theirtwo operands. They behave in the same way as the sub instructions, except thatthey set the condition codes without updating their destinations.

By using a PC-relativeencoding of the jump targets, the instructions can be compactly encoded (requiringjust 2 bytes), and the object code can be shifted to different positions in memorywithout alteration.

It is important to recognize that the suffixes forthese instructions denote different conditions and not different operand sizes. Forexample, instructions setl and setb denote “set less” and “set below,” not “setlong word” or “set byte.”

one for unsigned (mulq) and one for two’s-complement (imulq) multiplication.For both of these instructions, one argument must be in register %rax, and theother is given as the instruction source operand.

The different shift instructions can specify the shift amount either asan immediate value or with the single-byte register %cl.

As with themov instructions, the two operands cannot both be memory locations.

This operand can be either a register ora memory location.

The destination operand must be a register.

The ability of the leaq instruction to perform addition and limited forms ofmultiplication proves useful when compiling simple arithmetic expressions suchas this example.

local variables such as x are often kept in registers rather thanstored in memory locations. Register access is much faster than memory access.

we see that whatwe call “pointers” in C are simply addresses. Dereferencing a pointer involvescopying that pointer into a register, and then using this register in a memoryreference.

One important feature is that memoryreferences in x86-64 are always given with quad word registers, such as %rax, evenif the operand is a byte, single word, or double word.

logicallybe named movzlq, but this instruction does not exist. Instead, this type of datamovement can be implemented using a movl instruction having a register as thedestination. This technique takes advantage of the property that an instructiongenerating a 4-byte value with a register as the destination will fill the upper 4bytes with zeros.

in memory, to a register destination. Instructions in the movz class fill out theremaining bytes of the destination with zeros, while those in the movs class fillthem out by sign extension, replicating copies of the most significant bit of thesource operand.

The source operand designates a value that is immediate, stored in a register,or stored in memory. The destination operand designates a location that is either aregister or a memory address. x86-64 imposes the restriction that a move instruc-tion cannot have both operands refer to memory locations. Copying a value fromone memory location to another requires two instructions—the first to load thesource value into a register, and the second to write this register value to the des-tination.

The most general form is shown at the bottomof the table with syntax Imm(rb,ri,s). Such a reference has four components: animmediate offset Imm, a base register rb, an index register ri, and a scale factors, where s must be 1, 2, 4, or 8. Both the base and index must be 64-bit registers.The effective address is computed as Imm + R[rb] + R[ri] . s.

C declaration Intel data type Assembly-code suffix Size (bytes)

A final difference is that we see two additional lines of code (lines8–9). These instructions will have no effect on the program, since they occur afterthe return instruction (line 7). They have been inserted to grow the code for thefunction to 16 bytes, enabling a better placement of the next block of code in termsof memory system performance.

Its main feature isthat it is in a more readable textual format, as compared to the binary format ofmachine code.

reinterpret_cast 运算符并不会改变括号中运算对象的值，而是对该对象从位模式上进行重新解释

A namespace is a scope.C++ provides namespaces to prevent name conflicts.

But the other effect of unnamed namespaces is that all identifiers inside an unnamed namespace are treated as if they had internal linkage, which means that the content of an unnamed namespace can’t be seen outside of the file in which the unnamed namespace is defined.

One of the best things about classes is that they contain destructors that automatically get executed when an object of the class goes out of scope. So if you allocate (or acquire) memory in your constructor, you can deallocate it in your destructor, and be guaranteed that the memory will be deallocated when the class object is destroyed (regardless of whether it goes out of scope, gets explicitly deleted, etc…).

Three techniques to avoid losing critical information at half-precision: Full-precision master copy of weights. Maintain a full precision (FP32) copy of model weights that accumulates gradients. The numbers are rounded up to half-precision for forward & backward passes. The motivation is that each gradient update (i.e. gradient times the learning rate) might be too small to be fully contained within the FP16 range (i.e. 2−242−242^{-24} becomes zero in FP16). Loss scaling. Scale up the loss to better handle gradients with small magnitudes (See Fig. 16). Scaling up the gradients helps shift them to occupy a larger section towards the right section (containing larger values) of the representable range, preserving values that are otherwise lost. Arithmetic precision. For common network arithmetic (e.g. vector dot-product, reduction by summing up vector elements), we can accumulate the partial results in FP32 and then save the final output as FP16 before saving into memory. Point-wise operations can be executed in either FP16 or FP32.

two major memory consumption of large model training: The majority is occupied by model states, including optimizer states (e.g. Adam momentums and variances), gradients and parameters. Mixed-precision training demands a lot of memory since the optimizer needs to keep a copy of FP32 parameters and other optimizer states, besides the FP16 version. The remaining is consumed by activations, temporary buffers and unusable fragmented memory (named residual states in the paper).

It partitions optimizer state, gradients and parameters across multiple data parallel processes via a dynamic communication schedule to minimize the communication volume.

Asynchronous parallel (ASP): Every GPU worker processes the data asynchronously, no waiting or stalling. However, it can easily lead to stale weights being used and thus lower the statistical learning efficiency. Even though it increases the computation time, it may not speed up training time to convergence.

Bulk synchronous parallels (BSP): Workers sync data at the end of every minibatch. It prevents model weights staleness and good learning efficiency but each machine has to halt and wait for others to send gradients.