BLOGGER TEMPLATES AND TWITTER BACKGROUNDS »
Showing posts with label parallel processing. Show all posts
Showing posts with label parallel processing. Show all posts

Sunday, 16 December 2012

the GPU @ VPU

example: the GeForce6600 GT


CHARACTERISTICS:
  • A specialized processor efficient at manipulating and displaying computer graphics
  • fundamental in 3D games
  • optimized for raster graphics

GPU COMPUTING
WHAT IS GPU Computing?

  • the usage of a graphic processing unit (GPU) along with a CPU to accelerate general-purpose scientific and engineering applications
  • pioneered by NIVIDIA

BASICALLY, a (GPU + CPU) combination is godlike because 
  • CPU consists of a few cores more suited for serial processing
  • while the GPU consists of thousands of smaller, more efficient cores suited for parallel processing
  • serial portions of codes are run on the CPU, while the parallel portions are run on the GPU
by Lua Xin Lin B031210345

Saturday, 15 December 2012

HAZARDS (Pipelining)


  •   Hazards are problems with the instruction pipeline in CPU micro architecture that potentially result in incorrect  computation.


·              There are three types of hazards:
Ø  Data Hazard:
o   Occurs when instructions exhibit data dependence modify data in different stages of a pipeline.

o   There are three situations in which the data hazards can occur:
§  Read after write (RAW)-true dependency
§  Write after read (WAR)-anti-dependency
§  Write after write (WAW)-output dependency

o   RAW:
§  A situation where an instruction refers to a result that has not been yet calculated or retrieved
§  Occurs when an instruction is executed after a previous instruction has not yet been completely processed through the pipeline.
§  Eg:
ü  I1.R2<- R1+R3
ü  I2.R4<- R2+R3
ü  First instruction (i1)is calculating a value to be saved in register R2 and second instruction is going use that value to compute a result for register R4
ü  However, in pipeline, when we fetch the operand for the 2nd operation, result from the first is not yet been saved and hence we have data dependency…

 
Diagram for data hazards…
o   WAR
§  Occur when instruction 2 tries to write destination before it is read by instruction 1.
§  Represent a problem with concurrent execution.
§  Eg:
ü  I1.R4 <- R1+R3
ü  I2.R3<- R1+R2
ü  If I2 is completed earlier than I1 ,ensure that do not store the result of register R3 befreI1 has had a chance to fetch an operand.

o   WAW
§  I2 tries to read write an operand before written by I1
§  May occur in concurrent execution environment
§  Eg:
ü  I1.R2<- R3+R4
ü  I2.R2<- R1+R2
ü  Delay the WB(Write Back) of I2 until the execution of I1…
o   There are 3 ways to handle the data hazards:
o   Software: insert independence instruction(or no-ops)
o   Hardware: insert bubbles (stall the pipeline)
                   :data forwarding

Diagram of handling data hazards through software…

Diagram of handling data hazards through hardware(insert bubbles/stall the pipeline)…
Note: Pipeline stall
          To insure proper pipeline execution in light of register dependences, we must:
1.      Detect the hazards
2.      Stall the pipeline:
--prevent IF (do not want to lose any instructions) and ID (can’t continue until the dependent instruction complete correctly) stages from making progress
=do not write the PC (PCWrite=0);
=do not rewrite IF/ID register (IF/IDWrite =0);
 --inserts “no-ops” into later stages
=set all control signals propagating to EX/MEM/WB=0;

Diagram of eliminating data hazards via forwarding with stalling pipeline after loading….
Note:
Data forwarding…
=forwarding handles 2 types of data hazards which are EX HAZARDS & MEM HAZARDS.
=The third type hazards (WB HAZARDS)is already handled by using a transparent reg file in which this reg file allow the write data to be forwarded to the output if the register file is asked to read and write the same register in the same cycle…
=Forwarding method only is NOT enough to eliminate all the data hazards therefore it must works with pipeline stall just like the diagram shown above.
Ø  Structural Hazards…
o   Occur when a part of processor’s hardware is needed by two or more instructions at the same time.
o   Eg:
o   A memory unit that is accessed both in the fetch stage where data is written and/or read from memory.
o   Can be resolved by :
o   Separating the component into orthogonal unit (eg: separate cache)
o   Bubbling the pipeline


Diagram of resolving structural hazards via bubbling the pipeline…

Ø  Control hazards (branch hazards)
o   Occurs with branches
o   Can cause greater performance lost than data hazards
o   When a branch is executed it may or may not change the PC (to other value than its value+4)
o   It is said taken branch if the branch is changing to its target address and vice versa…
o   If the instruction I is a taken branch, then the value will not change until the end of MEM stage of the instruction execution in the pipeline
o   A branch causes 3 cycle stall in processor pipeline:
=One cycle repeated IF (IF is redundant if branch is not taken)
=Two idle cycle
o   The three clock cycle lost for every branch is a significance loss and the machine with branch stall with 30% branch frequency   only achieve half of the speedup of pipelining
o   Reducing the branch penalty becomes critical…
o   To avoid the control hazards :
=insert pipeline bubble which guaranteed to increase latency
=use branch prediction and make educated guesses about which instruction to insert



Chong Cai Ning

B031210080

PIPELINING


·         In computing, pipelining is a set of data processing elements connected in series therefore the output of one element is the input of the next element.

·         The above statement means the microprocessor begins to execute second instruction before the first instruction complete.


·         The pipeline is divided into segments and each segment can execute its operation concurrently with the other segments.

·         That is , when a segment complete an operation, it passes the result to the next segment in pipeline & fetches the next operation from the preceding segment.


·         For a microprocessor that without the pipelining, the second operation will only started when the first operation fully completed.

·         Therefore, the microprocessor which with the pipelining will be more efficient and faster compared to the one without pipelining…


·         Below is a diagram of microprocessor with a pipelining…

·         for 4 loads:
Ø  8/3.5 or (4(4)/(4+3))=2.3
·         Non-stop:
Ø  4n/(n+3)=4(16)/(16+3)=3.347≈4 stages

·         Although the pipelining initially formerly a feature only of high-performance & RISC-based microprocessor, now is commonly in microprocessor used in personal computers. (For examples,  Intel’s Pentium uses pipelining to execute as many as six instructions simultaneously….)
·         Besides, pipelining also called pipeline processing.
·         Eg:
Ø  DRAM:
o   Memory loads the requested memory contents into small cache composed of SRAM and then immediately begins fetching the next memory.
o   Creates two stages:
§  Stage1: data is read from or written to the SRAM
§  Stage2:data is read from or written to memory
Ø  DRAM(c’td):
o   Usually combine with another performance technique called burst mode
o   And the two techniques together called pipeline burst cache
·         MIPS Pipelining:
o   Five stages (one step per stage):
o   IF: instruction fetch from memory
o   ID: instruction decode and register read
o   EX: execute operation or calculate address
o   MEM: access memory operand
o   WB: write result back to register

Chong Lee Man
B031210367

DISTRIBUTED MEMORY


DISTRIBUTED MEMORY
·         Refers to multiple-processor computer system in which all processor has its own memory.
·         Computational task can only operate an local data
·         One or more remote processor must be communicated by computational tasks if remote data is required.
==============================================================
·         Architecture of a distributed memory:
=a processor
=a memory
=some form of interconnection that allow programs in each processor to interact with each other…
·         Below is a diagram of architecture of distributed memory of 3 computers:

·         The interconnect can be organized with point-to-point links or separate hardware which can provide a switching network.
·         Network topology=key factor determining how the multi-processor machine scale.
·         Implementation of links between nodes:
=using some standard  network protocol (eg: Ethernet)
=bespoke network links (used in Transputer)
=dual ported memory
===============================================================
·          In distributed memory ,there is also distributed shared memory in which each node of cluster has access to a large shared memory in addition each node’s limited private memory.
·         There are comparison between shared memory , distributed memory and distributed shared memory:
=(distributed) shared memory offer a unified address space in which all data can be found
=distributed memory can exclude race conditions and force the programmer to think about the data distribution.
=distributed (shared) memory easier to design a machine that scales with algorithms
=Distributed shared memory hides the mechanisms of communications (does not hide the latency of communication)…

Ku Man Yi
B031210161

DESIGNING PARALLEL PROGRAMS (1)


  Parallel programming:
=utilizes concurrency to achieve high performance computing
=today becoming mainstream paradigm in regular day-to-day information processing.
---energized by widespread availability of multi-core multiprocessor and cost-effective server clusters
=fast becoming an essential developer skill as knowing the basic concepts helps in a better comprehension of the complexity
·         Parallel program:
=are built by combining sequential programs
---allow independent sequential programs to run in parallel & produce partial, results that then are merged into final solution via patterns.

..figure of parallel computer-shared memory and distributed memory models

Designing parallel program:
          To understand better the design, a model at a higher level than the shared-memory model or the distributed-memory model are used.
·          This is the task/channel model.
·          A task is a program, its local memory, and a collection of I/O ports in which is represented by a process in an operating system (threads are contained in processes).
·         The local memory contains the program instruction and data.
·         A task can send local data values to other tasks via output ports & receive data values from them via input ports.
·         A channel == message queue that connects the output of one task to the input port of another.
·         Data values appear at the input port in the same order in which they are placed in the output port at the other end of the channel.


…figure of conceptual view of task/channel model.

Wong Poh Ling
B031210033

Parallel Processing: Parallel Computing



PARALLEL COMPUTING:


the simultaneous usage of processing elements to solve a computational problem: 

  • To be run using multiple CPUs 
  • A problem is broken into discrete parts that can be solved concurrently 
  • Each part is further broken down to a series of instructions 
  • Instructions from each part execute simultaneously on different CPUs



To put it simply,

pipelining 
is the act of breaking a task into steps performed by different processor units,
with inputs streaming through, much like an assembly line; a type of parallel computing

by WONG POH LING

Limitations of Parallel Processing: Amdahl's Law



Amdahl's Law

states that the potential program speedup is defined by the fraction code (P) that can be parallelized



  • If none of the codes can be parallelized, P=0; S=1. (no speedup)
  •  if all the codes are parallelized, P=1; speedup is infinite
  • if 50% of the codes are parallelized,  
  • When there are N processors,





By KU MAN YI B031210161

DESIGNING PARALLEL PROGRAMS (2)

PARTITIONING@ DECOMPOSITION


  • breaking the problem into discrete 'chunks' that can be distributed to multiple tasks
  • two types: 

  • DOMAIN DECOMPOSITION
    • data is decomposed
    • each parallel tasks then works on their portion of data














  • FUNCTIONAL DECOMPOSITION

  • - focuses on the computation that is to be performed
    • the problem is decomposed according to the work that must be done
    • each task performs a portion of the overall work




COMMUNICATION

  • cost of communication
    • inter-task communication always implies overhead
    • communication between task typically requires synchronization between tasks, which results in time spent 'waiting' rather than doing work
  • latency vs. bandwidth
    • latency : time taken to send minimal message (0 bytes) across two points. Expressed in microseconds.
    • bandwidth: the amount of data transferred over time (Mbps or Gbps)
    • concept : package small messages into large message to increase the effective communication of bandwidth
  • scope of communication
    • point to point
    • collective

LOAD BALANCING

  • distributing work evenly among all tasks so that all tasks are kept busy ALL THE TIME
  • minimization of task idle time
  • Achieving LOAD BALANCE
    • equally partitioning the work each task receives
      • for array/matrix operations (each task performs similar work) : evenly distribute data set among tasks
      • for loop iterations (similar work is done in each iteration) : evenly distribute iteration across tasks
    • dynamic work assignment
      • certain classes of problems result in load imbalances even if data is evenly distributed
        • sparse array: some tasks have actual data to work on while others mostly have 'zero's
        • adaptive grid method: some tasks may need to refine their mesh while others don't
      • when the amount of work each task does is intentionally variable, it is better to use scheduler-class-pool
      • scheduler task pool: after each task finishes its work, it is lined up for another task 
BY LUA XIN LIN B031210345