Identifying parallelism

A formal way to identify parallelism in an activity is to draw a task dependence graph in a directed graph in which each vertex represents a task to be completed. An edge from vertex u to vertex means that task u must be completed before task v begins, so that task v "depends on" u. If there is no path from u to v, then the tasks are independent and may be performed concurrently. Consider the following problem: Alice is the leader of a crew of workers who maintain a large estate. There are four principal tasks: mowing the lawns, pruning the trees and hedges, repairing the fences, and inspecting the work to ensure it has all been done satisfactorily. Mowing must be completed before the work is inspected, as must the pruning and fence repair. The estate has a security system which must be switched off before work commences (i.e. before Alice and her team arrives), and switched on again after the team leaves.

• Draw the dependence graph corresponding to the above problem, showing all the tasks involved. (In a project management plan, this scheme is often referred to as a "work breakdown structure").

• Alice has 8 people in her crew, including herself. (The crew members are: Alice, Bert, Cressida, Dominic, Edgar, Frank, Gus and Harriet). Alice will be solely responsible for inspecting the work, but decides that she herself and three other people (Bert, Dominic and Gus) will mow the estate's four lawns (referred to as north, south, west and east lawns, each of which are of equal area), two other people (Cressida and Frank) will prune the trees, whilst Edgar and Harriet will repair the fences. Redraw the graph to show the allocation of the crew to particular tasks. (Hint: a single task in the original graph may be come multiple tasks in the revised version, each of which is performed by a particular person).

• Alice is a fast worker, and can mow any of the lawns in one hour, as can Dominic. Frank and Gus can complete any of the manual tasks in two hours. Bert, Cressida, Edgar and Harriet take three hours to do their work. If the manual work starts at 10:00 a.m. in the morning, at what time scan Alice inspect the work? In your answer, refer to the dependence graph showing the allocation of crew to tasks.

Since mowing is done first and then all team members start the work simuntaneosly and Alice can only inspect after each has finished their task the time taken by the slowest team members will be seen here.

Harriert/Bert/Credessia and Edgar take 3 hrs each to complete their task.

The manual work starts at 10.00 AM so the inspection will start 3+3 =6 hrs after that.

Posted Date: 6/29/2012 2:06:10 AM | Location : United States

Ask an Expert

Related Discussions:- Identifying parallelism, Assignment Help, Ask Question on Identifying parallelism, Get Answer, Expert's Help, Identifying parallelism Discussions

Write discussion on Identifying parallelism
Your posts are moderated

Write your message here..

Related Questions

Designing issues in a network-scalability, Scalability Scalability is t... Scalability Scalability is the ability of the system to adapt to increased service load. A scalable system will respond more gracefully to increased load than a non scalable on

Define thrashing, Define thrashing. Thrashing is the accident of high p... Define thrashing. Thrashing is the accident of high page traffic and low CPU utilization. It is observed that the cause of thrashing is an under-commitment of memory to program

What resources are utilized when a thread is created, Q. What resources are... Q. What resources are utilized when a thread is created? How do they vary from those used when a process is created? Answer: For the reason that a thread is smaller than a pr

Error detection in operating system, Q. Error detection in operating system... Q. Error detection in operating system? Error detection- Error detection take places at both the hardware and software levels. At the hardware level every data transfers must b

Processes, draw a state diagram showing the transissions of a process from ... draw a state diagram showing the transissions of a process from creation to termination

List the coffmans conditions that lead to a deadlock, List the Coffman's co... List the Coffman's conditions that lead to a deadlock. Mutual Exclusion : Only one process might be use a critical resource at a time. Hold & Wait: A process may be alloc

What is a resource-allocation graph, What is a resource-allocation graph? ... What is a resource-allocation graph? Deadlocks can be explained more precisely in terms of a directed graph called a system resource allocation graph. This graph having of a se

search tree generated by hill-climbing search, Show the search tree genera... Show the search tree generated by Hill-Climbing search (text figure 4.2, page 122; or Local Search lecture, slide 6) for each of the two heuristics (a) and (b) applied to the follo

Memory organization and decoding, In a  p system each part (RAM, ROM, I/O) ... In a  p system each part (RAM, ROM, I/O) has a unique set of numbers. The allocation of these numbers is usually stated in the form of a memory map. This is a plot of data bus agai

Illustrate scope of consumer behaviour, Q. Illustrate Scope of Consumer beh... Q. Illustrate Scope of Consumer behaviour ? Scope of consumer behaviour is extremely wide due to following reasons: >>Ever rising intensifying competition. >>Additional a