Synchronized Access to Shared Memory in a Multi Core Computer - Lab Report Example

Abstract A Chip-Level Multiprocessor (CMP) or a Multi-Core Processor has two or more independent CPUs integrated on a single Integrated Circuit (IC). Such an arrangement is useful since it allows two or more different operations to run simultaneously increasing the processing output. However, in such an arrangement it is very necessary to maintain control over memory access since these processes could be inter-dependent and the sequence of their execution could be critical. This can be achieved by using Hardware and Software co-ordination. Various techniques which can be used to achieve this are discussed in the following paper. Synchronized Access to Shared Memory by Multiple Concurrent Threads in a Multi Core Computer A multi-core processor (or chip-level multiprocessor, CMP) combines two or more independent cores (normally a CPU) into a single package composed of a single integrated circuit (IC). The below diagram “Dual CPU Core Chip” (Schmitz, 2004) gives an idea about it. The principle behind current Multi-Processing (MP) systems is that computations requiring large amount of CPU usage could be broken up into many relatively independent parts. These parts, called threads, while being executed simultaneously, could either be of the same or different process. Since these threads could be inter-dependant, issues of memory architecture and in particular memory consistency and cache behavior are ‘key’ to both correctness and performance in multi-processing systems. Multi-Core Processors (CMPs) could be broadly classified as Uniform Memory Access (UMA) processors in which all the CPUs are able to access all the memory with no specific preference or Non-Uniform Memory Access (NUMA) processors, where each CPU may have its own special memory area. A system may maintain memory consistency using hardware or using a combination of hardware and software techniques. Hardware can provide a particular memory ordering guarantee, (hardware will maintain the sequential nature of program memory accesses), while software can be used supplement hardware-provided memory ordering by forcing additional ordering restrictions at desired times. The memory ordering scheme implemented is a design choice involving a tradeoff between hardware complexity, software complexity, and the desired ability to cache and buffer data. Non-Uniform Memory Access (NUMA) Architecture Refer Diagram “NUMA Architecture.” (Watson, n.d., p. 4) In NUMA architecture a processor can access its own local memory faster than non-local memory that is, memory local to another processor or memory shared between processors. In this type, all the MPs may or may not be of similar capacity (Asymmetric Multi Processing). Communication between processors is often based on use of shared memory between those processors. An ‘Inter Process Interrupt’ (IPI) allows CPUs to generate notifications to other CPUs to invalidate entries for a shared region or to request termination. Uniform Memory Access (UMA) Architecture Refer Diagram “UMA Architecture.” (Watson, n.d., p. 3) When multiple processors can access the same shared memory, the MP system has to make sure that the ordering of memory access from one processor is made visible to the other processors. Memory Fencing One way to achieve ‘Cache Coherence’ in a MP environment would be by using ‘Fencing’ technique. Refer Diagram ‘MFDA and MFDR Instruction” (Mittal, 1997, p. 26). In this technique, MP system (11) access and release of shared memory space (15) is done using two special instructions – MFDA and MFDR. The Memory Fence Directional – Acquire (MFDA) (16) instruction locks the specified area from being accessed by other processors. Once the operation is over and data can be released, the Memory Fence Directional – Release (MFDR) (17) instruction is issued. Since an MFDA instruction ‘locks’ the shared data until its use is over and an MFDR instruction is issued, it ensures that no two simultaneous accesses to the shared memory space take place and hence, ‘Cache Coherence’ is always maintained in the shared memory space. Access Ordering Control To achieve ‘Synchronized’ access to multiple threads in a MP system, not just ‘Cache Coherence’ but also ‘Access Ordering Control’ or the order in which data is accessed is very important esp. when two accesses have to be done in a particular sequence. The various ‘Memory Consistency Models’ proposed are: Sequential consistency, Processor consistency and Weak consistency. Sequential Consistency As defined by ‘Lamport’ “A system is ‘Sequentially Consistent’ if the result of any execution is the same as if the operations of all the processes were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program” (as cited in Gharachorloo, Lenoski, Laudon, Gibbons, Gupta, Hennessy, n.d., p. 2). Refer Diagram “Sequential Consistency” (Mittal, 1997, p. 27) A necessary and sufficient condition for ‘Sequential Consistency’ is that before any LOAD or any STORE access is allowed to perform, all previous LOADs must be ‘globally’ performed and all previous STOREs must be performed. Processor Consistency ‘Processor Consistency’ relaxes some of the orderings imposed by ‘Sequential Consistency’. As proposed by Goodman, it requires that “writes issued from a processor may not be observed in any order other than that in which they were issued. However, the order in which writes from two processors occur, as observed by themselves or a third processor, need not be identical.” (as cited in Gharachorloo et al., n.d., p. 2) Refer Diagram “Processor Consistency” (Mittal, 1997, p. 28). It can yield better system performance, but since it is weaker than Sequential Consistency, it is not fool proof. Programmers must explicitly use synchronization rather than depending on the memory system. Conditions for ‘Processor Consistency’ are: “(A) before a load is allowed to perform with respect to any other processor, all previous load accesses must be performed, and (B) before a store is allowed to perform with respect to any other processor, all previous accesses (loads and stores ) must be performed.” (Gharachorloo et al., n.d., p. 2) Weak Consistency A weaker consistency model is where memory request ordering is related to synchronization points. They distinguish between ordinary shared accesses and synchronization accesses. Synchronization accesses are used to control concurrency between several processes and to maintain the integrity of ordinary shared data. Refer Diagram “Weak Consistency” (Mittal, 1997, p. 28) For a ‘Weak Consistency’ we require that: “(A) before an ordinary load or store access is allowed to perform with respect to any other processor, all previous synchronization accesses must be performed, and (B) before a synchronization access is allowed to perform with respect to any other processor, all previous ordinary load and store accesses must be performed, and (C) synchronization accesses are sequentially consistent with respect to one another. (Gharachorloo et al., n.d., p. 3). References Gharachorloo, K., Lenoski, D., Laudon, J., Gibbons, P., Gupta, A., Hennessy J. (Eds.) Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors. CA: Computer Systems Laboratory Stanford University. Retrieved December 19, 2008 from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.8112 Mittal, Milind (1997, December 12) Controlling Memory Access Ordering in a Multi-Processing System. CA: World Intellectual Property Organization. Retrieved December 19, 2008 from http://www.freepatentsonline.com/EP1008053.html Schmitz, Dennis (2007, June 8) Dual core generic. Retrieved December 19, 2008 from http://en.wikipedia.org/wiki/File:Dual_Core_Generic.svg Watson, Robert (Eds.) Introduction to Multithreading and Multiprocessing in the FreeBSD SMPng Network Stack. Computer Laboratory University of Cambridge. Retrieved December 19, 2008 from http://www.watson.org/~robert/freebsd/netperf/20051027-eurobsdcon2005-netperf.pdf Read More