okay assalamu alaikum my very good morning to everyone okay so today we were going to the chapter lecture five okay which is the principles of further awareness design in the part two okay this one is actually continuously or from your decomposition technique which is the explosive decomposition okay exploratory decomposition is many cases uh decomposition problem goes hands in hand with this expression okay there they can protect them based on the problem okay mathematical uh their execute okay so this problem will typically involve the exploration so whether based on dedicated decomposed based on a problem can involve the exploratory enterprise searching of the state space of solution okay the minimum problem we need [Music] to 15 puzzles we show the sequence move into three move transform which is stated i initially stated [Music] [Music] [Music] okay [Music] [Music] okay so the problem of computing the solution in general is actually much more difficult [Music] space and municipal explore by generating various successes state of the current state and to view them as an independent task force okay [Music] [Music] [Music] [Music] [Music] [Music] up too much money to explore okay how can i explode okay and then yeah and then uh [Music] okay [Music] [Music] okay [Music] okay and okay so this is how this will be adela in the pendant so this is called an exploratory decomposition okay okay so [Music] [Music] um [Music] okay so it's very uh during many sentences of instances okay exploratory decomposed technique can change the amount of work done okay okay uh arrange the empty towels okay so there have been work done by the formula by relatively information so they wouldn't have a change between the world okay this change uh result okay really therefore changes me the super or the sub learners can't speed up okay so they are kind of processed okay i can't speed up the process okay so that is how we can be using a respiratory decomposition okay the next scenic are the last speculative decomposition okay this kind of method okay you have a 2m okay us plus one okay okay okay okay [Music] okay and then with the four of uh 4m so that's why there is when you speed up okay so that's why they gotta change the amount of voltage [Music] okay in some application okay depending okay guitar speculative okay in speculative decomposition some application it depends on the task which is known as a priori okay tasks are not known as a query for such application this is impossible to identify the independent tasks okay they are generally okay generally speculatively that they will satu we call it as a conservative approach okay the money conservative unfortunately okay they identify the independent tasks only relay they're guaranteed they do not have any dependency uh speculatively they do approach to conservative process to optimistic approach conservative approach their account identified independently guaranteed there's no dependency okay optimistic approach schedule okay concurrency manicure optimistic approach will require a rollback mechanism in the case of errors process of concurrency [Music] the task okay all right okay so a classic example of speculative concept is in discrete event simulation okay dynamic simulation discrete event so the central data structure is in the disk event submission is the time order event list okay time order okay based on uh even the list of events uh according to the time right so the even even young extracted the process in the time order the process and if required resulting event uh they are inserted back into the event list okay so eventually i can extract uh in time [Music] drive to work okay religion market lunch work some more okay drive back eat dinner and sleep so they do routinely they're delicious okay first second next person okay all right so that is because it discrete the top the top data type so this is called um speculative okay all right so each of this is by may be processed independently okay however in okay all right so uh so each of this event may be personal independence however in driving to work okay eventually driving to work okay okay you might end up unfortunate accident oh and not get to work at all okay uh so therefore actually drink of other events will have to be rolled back okay process okay you have to go roll back this situation okay all right that is fabulous okay so another simulations about the uh using a speculatively composite process of notes assembly the line or computer network through packet okay the task is stimulate the behavior of this network for various input and node so there i have a barrier is various input okay so you put up a chuck and the task 2 into a various input and nodes and then the delay parameters will become unstable for certain value for the service rate and also the queue size okay so they are they are kind of delayed so they will at that point they become unstable it's about uh because [Music] [Music] [Music] uh decomposition technique into mix okay uh so that's why you gotta hybrid okay so okay [Music] [Music] okay so the lab in this case event simulation they might be concurrent in task processing okay so the mix of speculative decomposition and data also work well okay all right evening [Music] one with our optimistic approach uh blend together okay all right so even the simple problem like finding a minimum list of numbers okay we can [Music] [Music] [Music] [Music] decompose this set of number okay into four okay okay okay okay and then to just kind [Music] [Music] okay so because you need okay so then then after saturday night we make some comparison okay all right uh so emily how we can lose a quick swot okay using data complete composition and also recursive function by using hybrid decomposition the hybrids are therefore combined technique decomposition technique okay okay more than one technique all right okay once the problem has been decomposed characteristic of this task okay critically impact the choice and also [Music] how good the algorithm is being used okay this generation the task size and also the size of data being associated with the task how does such data that society is uh associated with the past support okay okay let's look at the task generation task generation they can be identified the priority manipulative identified the main priority okay typically with the max operation matrix operation graph algorithm image processing application and other regularly structured problems the cd graph algorithm image processing so they fall under this static test channel this normally decomposes using data or recursive decomposition technique okay so static task generation [Music] [Music] [Music] must be identified depending on priority okay there is a score aesthetic the second one is we call a task dynamic task generation okay billy dynamic test generation a the minute tasks will be generated as we perform the computation so the task i can generate [Music] when we perform the computation so a classic example of this is in in-game playing which is a puzzle body okay [Music] actually can be in uniform luminance that does either can be a same size at a point non-uniform okay so non-universe may be such that they can be determined or it can be estimated as some other the example of this class include the discrete discrete optimization problem is it difficult to estimate the effective size of the state space [Music] associate with the task size auretta is associated with tasmania normally it can be a small it can be enlarged based on the context of the size of the test tube okay that is amplify the algorithm can easily communicate these tasks to other process dynamically color small contact times data process okay or alternately the minor algorithm may attempt to reconstruct the context and another processes as opposed to communicating the context of data okay so the contact us uh the last contact me we were touched with the task of the process okay they began to occupy the process okay all right can communicate in many ways okay so yeah associated with the digital for me static interaction dynamic interaction [Music] static interaction but when we have a dynamic interaction timing or interacting tasks cannot be determined by the query okay okay so this interaction is a bit harder to quote because especially as well we can see using a of task insulation we have regular interaction [Music] definite pattern okay normally in the graph sensor okay to the interaction [Music] we can define the pattern okay in the graph sensor okay so this pattern can be exploited for efficient uh implementation so e really irregular uh interaction demonic okay right so the irregular interaction is [Music] okay all right this is example of a simple regular static anesthetic okay cpu okay this is the task okay all right okay [Music] own independence task so they can be considered as a pixel so really they communicate all right okay so the multiplication of the sparse mat uh as fast metric with the vector is a very good example of static irregular interaction patterns interaction ground uh this is starting to irregular okay all right okay so the introduction may be a read only or read right okay so internationally are my others how they read one time at a point in backwards okay some other ability and right there color it only interaction again associated with the other tests in color rewrite block they interact task boolean as well as the volume modified data item associated with the other tasks so in general rewrite interactions are harder to code because since there are required additional synchronization primitives and as well okay right so the interaction may be in one way at a point two way okay so this is we call interaction one way or two we one-way interaction mean you initiate and accomplish by one of the two interaction tasks okay color two-way interactions okay involved in the introduction so my channel one note 30 so that's why this is example of irregular interaction okay uh so do you believe what we do okay uh two ways uh so two ways inflation okay so once a pro blam composed into concurrent assets [Music] [Music] [Music] to minimize the overheat okay the primary overhead come from the communication also idling that is the overhead of the mapping look at like into consistent duration when you do parallel then you choose the better platform okay so minimize this overhead often represent the contract eating objective okay so we assign all the work to one processor trivially we can minimize the communication but you can expense of the significant island okay there meaning uh belief uh communicating ideally so contradicting of the kind of ideally so mapping must must simultaneously minimize the idling that is load balance processor okay [Music] [Music] [Music] [Music] [Music] [Music] [Music] okay so for this to work we must have a good estimate of billy kitten about statement estimation good estimation okay even in this case the problem may be not be complete okay all right okay dynamic mapping pull up tasks are mapped to the process at the runtime okay by the process to support during the runtime again this may be because the tasks are generated at runtimes or they can also or that their sites are not known okay so that's why they they map critical runtime they take care of a precise visa process to the program tasks to support the pd account process make a run times about cannable thus you will be generated during the run time so other factors that determine the choice of technique including the size of data with the task and also the nature of underlying domains [Music] is [Music] [Music] to the combination of data practitioning and task graph partitioning okay all right getting out my chairman um mapping based on data partitioning okay combine data partition with the owner computes rule to partition the computation into a subtask okay so kitten partition the composition so the simplest data complete composition is [Music] so this is how they do a block distribution scheme with a higher dimension as well okay all right so block redistribution in example dance matrices a and b we can partition in the dimensional which is determined some either is a straight a communication overhead upon generally higher dimension decomposition allowed to use a larger number of processes whether you have a higher dimension of decomposition there might use large of number of nupolican the large number of processes mean total demand how your data is sharing in the then metrics of multiplication okay [Music] okay all right okay cyclic and block cyclic difference distribution if the amount of cycling and block cyclic distribution anything much money is being partitioned so the amount of computation associated with the data items very hard allah decomposition may lead to significant of low imbalance so a simple of yeah decomposition ade laguna gaussians elimination of dance matrices we decompose into 14 tasks okay so nuclear matrix [Music] okay all right so the block cyclic distribution color block cyclic deposition the variations of log distribution scheme can be used to eliminate the load imbalance and also the idling problem is problems okay so we can partition an array into many more blocks than the numbers of a variable for cells get a so the block will be assigned to the processes in the round-robin manner so that each process gets several non-agency block okay so there is [Music] um [Music] finish the process okay but do they go to the next task okay all right uh so any angela activate of matrix in the gaussian elimination changes okay so guitar assign the block okay into a block cyclic versions okay column k and the row okay and then each processor will receive the block okay so that processor i can receive the block in the different parts of the my three okay so kitakan kalikala again so setup me [Music] [Music] added a number of processes so you are then part process this uh block block process so you will get five so p zero p one p zero p one p1 alternate d okay and then p2 p3 p2p3 okay the block cyclic of the operation okay so the [Music] okay all right so this is a graph partitioning that's okay data decomposition okay in the case of sparse matrices block decompositions are more complex you may know it consider the problem of multiplying a sparse method with a vector so kitakang gunakan meter multiplies plus matrix to linear vector k vector with a matrices okay so the graph of matrix is very useful in total indicate of the work which is the number of work and also the communication with each degree of each node okay in this case we like to partition the graph to us as so we assign equals number of nodes to each process while [Music] randomly with different different colors new minimum h cutting so each of the day they added their own region again their own area with the minimum sony mirror so determine the optimal mapping of a general task dependency graph is n p must be complete problem so accident heuristic exists for the structured graph okay so this is a record uh the elastic of the potency graph in one viewer so how it the sparse metric by turning with the product the nankita assigns the type took up by the different process process each of the processes okay so process zero added uh depending computing part and then process one they are the completing part okay basically they are depending on slightly participating [Music] okay all right okay sometimes a single mapping technique is inadequate okay of the binary tree quicksort which is cannot use for the large number of processors for this reason task mapping can be used at the top level and the data partitioning with each level okay all right this process okay and then we combine okay so example after present at the top level with the data partitioning at the lower level so the top level of past partitioning this process into two uh okay then p seven okay then pc then p seventy to the combine kinda on p4 and p5 okay all right and then p zero and three one get the combination p2 then p3 okay so we combine so this each of the processes keep the account the block and keeping up with the terminal setup process okay data into lower level then at the upper level okay [Music] balancing is the primary motivation for the dynamic mapping yeah so therefore can be some other gunas centralized attack point distributed okay so color keta pakkai centralized i thought this centralized or distributed okay one has to become master and others will become asleep where we call centralized okay so ini and kitapaka smp uh okay so process are designed as a master or the slave okay processes to keep the bullet signs somebody they become a master or become a slave when the process run out of work centralizing military become asleep when process run up for work it requests the master for more work okay [Music] so therefore they requested a master into what more criteria lagging okay when the number of process that we believe one number of processes increase their master become a voltage so the slave account referred to the master to liberate this process a process may pick up a number of tasks okay chunk at one time and this is we call a chang again we talk we uh bagika in the process to cut it into a chunk and this we call it then up in the boiler the [Music] imbalance as well okay the number of skin can be have uh gradually decrease the chance size as the computation progresses number of screening have been used gradually decrease the chance quran can size the chunk as a complication progress so centralization centralized dynamic mapping does distributed dynamic mapping color distributed setup process tool can send or receive work from other processes [Music] okay for example we have this uh there are four critical questions how are sensing and receiving the process are paired together two months okay each verse is bullish [Music] okay so answer this question are generally the applications specific so we look at the sound this technique okay all right distributed distribution system which is uh uh what we [Music] so that we can reuse in the smaller time windows okay so my medicated structure computation kita can reuse the smaller time windows guitar account reduce the time we use eh minimize the volume of data exchange kurankan the size of data exchange demonia it will there is a course associated with each word that is being communicated so that's why you hunted sms you anticipate messaging image video somebody live okay all right so minimize the frequency of interaction okay so minimize differences of inflation where there is a start-up cost associated with each interaction okay uh this attack step two interaction to either across associate and give me that okay try therefore i take it to combine some interaction into one column so minimize the contention top and the hot spot you might not use this interesting it means to replicate data when necessary okay that is why i want to centralize our technical okay something they can decentralize okay so overlapping computation with interaction use a non-blocking communication okay kita gunakan multithreading kit refreshing to hide the latency okay and then do the sum replication data or computation and so replicates okay and then yeah which is they're replicating okay you open your uh data and also the computation use the group communication instead of point to point primitive okay among the process and also the tasks and then the muda okay communication into balaku ankita the miner we select decomposition and also the mapping technique guitar select decomposition and mapping technique and apply appropriate strategy in order to minimize the interaction okay operation on the different data so data para modernity normally aesthetically static similar operation type they have velocity in different data into a different data okay unique data parallel model color task graph model okay they are stacked dependency graph they monitor inter interrelation among the tasks are utilized okay to promote locality or to reduce interaction costs okay the miner the depth among the tasks to account uh low what's a general locality okay so task attacked us to the account utilize the locality and then reduce the interaction cost among the nodes okay so this is starting a dependency uh the interrelationship among the tasks could okay you try to utilize using locality and reduce the open interaction cost okay other than what the other model is leave okay must leave one atom process there is a 2gd master and another give the body kind to us for the process to support each other slave okay if this one can be static or dynamic okay i need to keep each and each we perform a sum task on it okay produces a consumer model through the sensation of process okay you could find the process here under successful spinning and that's a technique i can't perform some tasks on it okay or we can use the hybrid model hybrid modeling we can compose using multiple model and apply hierarchical hierarchically or multiple models applied sequentially to the different phases of parallel algorithm so foreign all the model topic you could okay add the different faces okay into apparel algorithm okay so that's all for the lecture five four parallel algorithm design okay so we you need to do some exercise that assignment given in the microsoft team