Sequential & Parallel & Grid Computing PDF

SEQUENTIAL & PARALLEL & GRID COMPUTING #08 Sequential Computers  For many years, computer CPUs only had a single core.  In the early 2000s, as processor clock speeds began to stagnate, CPU manufacturers needed to find other ways to increase processing performance.  In...

SEQUENTIAL & PARALLEL & GRID COMPUTING #08 Sequential Computers  For many years, computer CPUs only had a single core.  In the early 2000s, as processor clock speeds began to stagnate, CPU manufacturers needed to find other ways to increase processing performance.  Initially, they achieved this by putting multiple processors in high-end computers. While this was effective, it added significant cost to the computers. Sequential Computers  By combining processors on a single chip, CPU manufactures were able to increase performance more efficiently at a lower cost.  In the mid-2000s, dual-core and quad-core CPUs began replacing multi-processor configurations.  While initially only high-end computers contained multiple cores, today nearly all PCs have multi-core processors. Sequential Computers  A processor core ( “core”) is an individual processor within a CPU.  Many computers today have multi-core processors, meaning the CPU contains more than one core. Sequential Computers Deep Blue & Watson PARALLEL COMPUTING Parallel computing is a type of computing architecture in which several processors execute or process an application or computation simultaneously. Parallel computing helps in performing large computations by dividing the workload between more than one processor, all of which work through the computation at the same time. PARALLEL COMPUTING The most important reason of parallelization a sequential program is to run the program faster. Speedup is used to express how many times a parallel program works faster than a sequential one, where both programs are solving the same problem. Ts – best known sequential execution time Tp – parallel execution time 𝑇𝑠 n – number of processors 𝑆(𝑛) = 𝑇𝑝 (𝑛) PARALLEL COMPUTING  One single task needs 8 hours to complete  S = Ts / Tp = 8 / 4 = 2  (2 times faster) PARALLEL COMPUTING  One single task needs 8 hours to complete  S = Ts / Tp = 8 / 2 = 4  (4 times faster) PARALLEL COMPUTING  One single task needs 8 hours to complete  S = Ts / Tp = 8 / 1 = 8 (times faster)  Max value – n (no. of processors) 𝑇𝑠 𝑛∙𝑇𝑝 𝑆 = = =𝑛 𝑇𝑝 𝑇𝑝 𝑇𝑠 𝑇𝑠 𝑆 = = 𝑇𝑠 =𝑛 𝑇𝑝 𝑛 PARALLEL COMPUTING  What if not the entire job can be parallelized???  S = Ts / Tp = 12 / 8 = 1.5 (times faster) PARALLEL COMPUTING  What if not the entire job can be parallelized???  S = Ts / Tp = 12 / 6 = 2 (times faster) PARALLEL COMPUTING  What if not the entire job can be parallelized???  S = Ts / Tp = 12 / 5 = 2.4 (times faster) PARALLEL COMPUTING  What if not the entire job can be parallelized???  S = Ts / Tp = 12 / 4 = 3 (times faster)  S = 1 / α = 1 / (4 / 12) = 3 PARALLEL COMPUTING  Amdahl’s Law - speedup is limited by α – fraction of the serial part of the program, only 1- α of the program being executed in parallel T p = Ts   + Ts  (1 −  ) / p Ts Ts 1 p S= = = = T p Ts   + Ts  (1 −  ) / p  + (1 −  ) / p   ( p − 1) + 1 1 lim S = p →  PARALLEL COMPUTING  α = 20%, 4 processors T p = Ts  0.2 + Ts  0.8 / 4 = 0.4  Ts Ts 1 S= = = 2.5 0.4  Ts 0.4  Max S = 1 / 20% = 5  if we add far more processors PARALLEL COMPUTING PARALLEL COMPUTING In order to obtain a faster program, we need to: - reduce to the minimum the fraction that cannot be parallelized - to assure the load balance of the tasks at the processor level - to minimize the times dedicated for communication and synchronization Sequential execution Parallel execution Sequential execution Parallel execution P1 P1 P2 P3 P4 P1 P1 P2 P3 P4 20% sequential 20% sequential 20% 20% 20% 20% ~20% ~20% ~20% ~20% 100% sequential 100% sequential GRID COMPUTING A grid is a collection of machines that contribute any combination of resources as a whole. Basically, grid computing represents a new evolutionary level of distributed computing. It tries to create the illusion of a virtual single powerful computer instead of a large collection of individual systems connected together. These systems are sharing various resources like computing cycles and data storage capacity. GRID COMPUTING A grid is a collection of machines that contribute any combination of resources as a whole. Application jobs Execution queue Scheduler and subjobs... Computer Computer Computer Collecting results GRID COMPUTING Desktop machines from most organizations are underutilized because they are busy less then 5% of time. Grid computing is able to increase the resource usage efficiency due to a better balance of resource utilization. If an application is grid-enabled, it could be moved to an idle computer from the grid whenever the host computer is busy. GRID COMPUTING If an application is written to use algorithms that can be divided into independent parts than each part could be executed on a different machine in the grid. This is why the grid computing offers a high potential for massive parallel CPU capacity. This huge computing power obtained by the use of the grid is driving a new evolution in various industries like financial modeling, oil exploration, bio-medical field, etc. GRID COMPUTING Not every application is suitable for running in parallel on a grid. Some applications simply cannot be parallelized. For others, it can take a large amount of work to modify them to run concurrently. Bandwidth becomes a critical resource that can limit the performance of the entire grid network. GRID COMPUTING  Opportunistic Supercomputing is a form of networked grid computing - a "super virtual computer" of many volunteer computing machines performs very large computing tasks.  The fastest grid computing system is the distributed computing project Folding@home (F@h).  F@h reported 101 petaFLOPS in 2020.  Summit - a supercomputer by IBM, one of the fastest supercomputer in the world, 148 petaFLOPS in 2020. GRID COMPUTING  SETI@home is a scientific experiment that uses Internet- connected computers in the Search for Extraterrestrial Intelligence (SETI).  SETI uses radio telescopes to listen for narrow- bandwidth radio signals from space.  Such signals are not known to occur naturally, so a detection would provide evidence of extraterrestrial technology. GRID COMPUTING  SETI uses radio telescopes to listen for narrow- bandwidth radio signals from space. GRID COMPUTING  1110 TFLOPS (10^12) ≈ 1.11 PFLOPS (10^15)  Millions of volunteers, in 226 countries, have downloaded the SETI@home screensaver.  The SETI@home volunteers have formed one our planet's most powerful supercomputers and have enabled the world’s most sensitive SETI search GRID COMPUTING  SETI experiments are trying to determine whether other intelligent, technologically capable, life exists in the universe, to answer the question "Are we alone?" or "Is anybody out there?"  The question "Are we alone?" touches on many disciplines, including physics, astronomy, chemistry, biology, engineering, and computer science. GRID COMPUTING  The Folding@home project (FAH) is dedicated to understanding protein folding, the diseases that result from protein misfolding and aggregation, and novel computational ways to develop new drugs in general.  “By downloading the Folding@home software you are supplying us with the computer power we need to find new cures. And by spreading the word you’re giving even more people the chance to contribute. In our book, that certainly makes you one in a million.” #09 – The End  Start Folding  The Folding@home software runs while you do other things.  While you are going about your everyday activities, your computer will be working to help us find cures for diseases like cancer, ALS, Parkinson’s, Huntington’s, influenza and many others.