Branch & Bound, Graphical Models and Structured Grids patterns

Branch & Bound

This pattern is used for problems where you have a very large space and you need to search to make a decision or find an optimal solution. Of course the space is too large for enumerating every point.

In order to find the solution to the problem, this pattern has four operations:  Branching, Evaluation, Bounding and Pruning.
This kind of problems are good for parallelism, even thou synchronization is complicated. You will want to reduce communication and increase computation.

Graphical Models

This pattern gave me a bad impression, because I thought I was going to read about graphics rather than statistics and probabilities. Also as some classmates mentioned, it lacked of a good and clear example.

Structured Grids

This pattern was better written I think, at least it had several examples (thou I missed source code!). The main idea is to decompose (using geometric decomposition) the problem into smaller arrays and perform operations over the arrays in parallel.

The double buffering and adaptive mesh refinement idea was very interesting to me and seems to be very useful for image processing.

Publicado en CS 527,English,Software Engineering | Sin comentarios

Questions on Task Parallelism, Recursive Splitting and Discrete Event patterns

This Tuesday I’ll be leading the Advanced Topics of Software Engineering class at the University of Illinois at Urbana-Champaign. People will blog about the following questions, which will also be discussed in class.

Task Parallelism

  1. When you first saw this pattern title, did you feel like you knew the subject beforehand? After reading the pattern, did you confirm your impression or did it surprise you? how?
  2. In what category falls this pattern?
  3. What platform do you have more experience programming parallel applications on? And what Task Management Mechanism? (Jobs over Networks, OS Processes, SW Task Queue, HW Task Queue)
  4. Do you think that the lack of new hardware is preventing us of reaching better run times?
  5. Do you think that this patterns requires you to learn more about hardware platforms in order to make a correct implementation?
  6. Do you agree with the mapping the author made for the Monte Carlo example? Can you think of something else?

Recursive Splitting

  1. How to control task granularity in this pattern?
  2. In which cases do you prefer to have a good load balancing rather than efficient tasks? Can we find the equilibrium?
  3. Can you think of any other popular algorithm (besides Selection Sort) which this pattern can not be applied to?
  4. The authors mention the idea of composing the Data Parallelism pattern inside of the Recursive Splitting pattern. Can you think of other patterns composition?
  5. The authors mention that the ideas behind the Fork/Join and Task-queue strategy patterns are essential to any developer who wants an efficient implementation of the Recursive Splitting pattern. Why?

Discrete Event

  1. In the context of asynchronous communication of events, the authors mention two environments: message-passing and shared-memory. Which environment are you more familiarized with? Which one you like most?
  2. Can you give examples of tasks which care about the order in which events arrive? Which approach (optimistic or pessimistic) would you use to deal with the ordering constraint in each one of those examples and why?
  3. Do you agree with the authors on that, often, the best approach to deal with deadlocks is to use timeouts instead of accurate deadlock detection?
  4. The authors encourage us not to confuse this pattern with the Event-based, Implicit Invocation pattern. Do you see any more differences beside the mentioned by the Discrete Event pattern authors?

Thank you very much.

Publicado en CS 527,English,Software Engineering | Sin comentarios

Sitios de interés