http://parlab.eecs.berkeley.edu/wiki/ 2009-11-24T18:30:43-08:00 http://parlab.eecs.berkeley.edu/wiki/ http://parlab.eecs.berkeley.edu/wiki/lib/images/favicon.ico text/html 2009-10-26T12:08:43-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/actors?rev=1256584123 An important class of object oriented programs represents the state of the computation in terms of a set of persistent objects. These objects encapsulate the state of the computation and include the fundamental operations to solve the problem as methods for the objects. In these cases, an effective solution to the concurrency problem is to make these persistent objects distinct software agents (the actors) that interact over distinct channels (message passing). text/html 2008-12-06T10:10:34-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/agent_and_repository?rev=1228587034 Name Agent & Repository Problem Many problems feature a large set of data, which is operated on by many different independent tasks. How can this be efficiently and correctly supported? Context Consider a large shared data structure. This structure might contain source code, a set of learned clauses in a Boolean satisfiability solver, or a full-blown, general-purpose database. The computation requires that many independent tasks be able to perform operations on this structure. The … text/html 2009-02-15T10:32:16-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/backtrack_branch_and_bound?rev=1234722736 Name Branch & bound Problem We have an extremely large space which we need to search to make a decision or to find an optimal solution. The space is so large that enumerating every point in the space is infeasible. How do we search the space efficiently? text/html 2009-02-24T13:41:57-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/backtrack_branch_and_bound_comments?rev=1235511717 Comments from February workshop: we have to settle on the name for this pattern. Does it include the word “Backtrack”? Or do we just call it “branch and bound”. Name: Problem: Context: Forces: Solution: Invariants: Example: Known uses: Related patterns: References: Authors: text/html 2009-09-28T15:44:37-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/blogs?rev=1254177877 Ade Miller: <http://www.ademiller.com/blogs/tech/> Michael McCool <http://blogs.rapidmind.com/2009/05/15/structured-patterns-as-a-standard-for-high-level-parallel-programming/> Michael Wrinn <http://software.intel.com/en-us/blogs/2008/12/08/creating-a-pattern-language-for-parallel-programming-the-evolving-view-from-berkeley/> text/html 2009-10-26T12:08:06-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/bsp?rev=1256584086 Managing computations and communications plus overlapping them to optimize performance can be very difficult. When the computations break down into a regular sequence of stages with well defined communication protocols between phases, a simplified computational structure can be used. One such structure is the BSP model of computation described in [Valiant90]. In this solutions, a computation is organized as a sequence of super-steps. Within a super-step, computation occurs on a local view of… text/html 2009-01-20T11:24:20-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/bulk_synchronous?rev=1232479460 Name Iterative Refinement Problem Many computations consist of a sequence of high level steps which repeat until some exit condition is met. Within each step, a number of mostly independent computations occur. How do you exploit the concurrency implied by this computational structure? text/html 2009-03-19T12:44:16-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/circuitcomputationpattern_comments?rev=1237491856 We want to separate specification(basic gates/RTL) from implementation(standard cell gates or instructions). The mapping from one to the other is a synthesis/compilation problem. The key difference between compilation to gates from compilation to instructions is that routing/selecting wires is essentially free for gates, but currently extremely expensive for instructions (i.e. you can do >>128 bit ops per bit insertion/route). text/html 2009-03-15T21:58:10-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/circuits?rev=1237179490 Revised: 03/15/2009 text/html 2009-04-07T11:45:57-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/class?rev=1239129957 Object Tracking Pattern Mining text/html 2009-04-08T13:40:42-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/collective_communication?rev=1239223242 BorYiing text/html 2009-10-21T14:36:08-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/contributors?rev=1256160968 The Contributors Kurt Keutzer Professor at UC Berkeley keutzer@gmail.com Tim Mattson timothy.g.mattson@intel.com Ralph Johnson Professor at U of Illinois johnson@cs.uiuc.eduRuss Rufer Silicon Valley Patterns Group russ@pentad.com Tracy Bialik tracy@pentad.com Terry Ligocki Applied Numerical Algorithms Group… text/html 2009-10-26T12:03:54-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/data_parallelism?rev=1256583834 Some problems are best understood as parallel operations on the elements of a data structure. When the operations are for the most part uniformly applied to these elements, an effective solution is to treat the problem as a single stream of instructions applied to each element. This pattern can be extended to a wider range of problems by defining an index space and then aligning both the parallel operations and the data structures around each point in the index space. text/html 2009-02-25T14:56:05-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/dense_linear_algebra_comments?rev=1235602565 Discussion: 1. Focus on how dense linear algebra is used - how to take advantage of matrix properties to optimize for solving dense linear algebra problems text/html 2009-04-06T21:27:11-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/digitalcircuits?rev=1239078431 text/html 2009-02-24T13:57:50-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/digitalcircuits_comments?rev=1235512670 this pattern defines a computaition not a parallel algorithm strategy. It also is only used by one higher level pattern, ie. the circuits pattern. Hence, i strongly believe we should get rid of this pattern. text/html 2009-05-05T14:00:47-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/distributed_array?rev=1241557247 Distributed array: The array is a critical data structure in many problems. Operating on components of the array concurrently (for example, using the geometric decomposition pattern) is an effective way to solve these problems in parallel. Concurrent computations may be straightforward to define, but defining how the array is decomposed among a collection of processes or threads can be very difficult. In particular, solutions can require complex book-keeping to map indices between global indi… text/html 2009-02-15T01:23:04-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/dynamic_programming?rev=1234689784 This page is out of date. Refer to the [PDF file]. Name Dynamic Programming Abstract Many problems appear with natural optimal substructures where by optimally solving a sequence of local problems, one can arrive at a globally optimal solution. There can be significant parallelism in solving independent locally optimal solutions. How can we organize data and computation to efficiently arrive at the globally optimal solution? text/html 2009-02-18T15:37:58-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/dynamicprogrammingcomments?rev=1235000278 Comments from February workshop: Name: Problem: Context: Forces: Solution: Invariants: Example: Known uses: Related patterns: References: Authors: text/html 2009-04-29T15:07:15-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/find_unique?rev=1241042835 Jike, Youngmin, Katya text/html 2008-12-06T10:17:41-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/finite_state_machines?rev=1228587461 Name Finite State Machines Problem To Satish: What about FSMs as transducers? How does this constrain output behaviors? In many situations the proper behavior of a system can naturally be described by a language of finite, or perhaps infinite, strings. The problem is to define a piece of software that distinguishes between valid input strings (associated with proper behavior) and invalid input strings (improper behavior). The system may have a set of pre-defined responses to proper input and… text/html 2009-10-26T12:05:46-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/forkjoin?rev=1256583946 The problem is defined in terms of a set of functions or tasks that execute within a shared address space. The solution is to logically create threads (fork), carry out concurrent computations, and then terminate them after possibly combining results from the computations (join). text/html 2009-03-16T12:29:14-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/geometric_decomposition?rev=1237231754 Problem How can an algorithm be organized around a data structure that has been decomposed into concurrently updatable “chunks” ? Context Many important problems are best understood as a sequence of operations on a core data structure. There may be other work in the computation, ut an effective understanding of the full computation can be obtained by understanding how the core data structures are updated. For these types of problems, often the best way to represent the concurrency is in te… text/html 2009-02-25T14:59:14-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/geometricdecomposition_comments?rev=1235602754 Source: Dense Linear Algebra Pattern (page 4) Author: Eric Battenberg Blocked Approach More sophisticated algorithms construct the product hierarchically from multiplications of smaller matrix blocks [7]. By computing outer products on small blocks of the input and output matrices, we can more eectively exploit spatial locali text/html 2009-02-24T13:38:25-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/glossary?rev=1235511505 Berkeley Pattern Language Glossary Algorithmic Framework: Algorithmic frameworks are application agnostic, algorithm dependent and platform agnostic (they help build Application Frameworks efficiently) Application Framework: Application frameworks are application dependent, algorithm dependent and platform agnostic (they help build Applications efficiently) text/html 2008-12-06T10:14:46-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/graph_algorithms?rev=1228587286 Name Graph Algorithms Abstract Many problems can be abstracted into vertices and edges, where the vertices represents objects, and the edges relations between objects. How can we efficiently analyze and manipulate these graphs in an efficient scalable way? text/html 2009-04-08T19:53:02-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/graphpartitioncomments?rev=1239245582 Graph partitioning comments I worry that this problem statement could almost work just as well for the “graphical algorithms’ pattern. It needs to be more narrowly focused. How about: * For a problem represented in terms of a graph, how do we decompose this graph into sub-graphs so we can efficiently exploit the concurrency in the problem? text/html 2009-04-28T13:03:37-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/iterative_refinement?rev=1240949017 Name Iterative Refinement Problem Many computations consist of a sequence of high level steps which repeat until some exit condition is met. Within each step, a number of mostly independent computations occur. How do you exploit the concurrency implied by this computational structure? text/html 2009-04-13T19:06:19-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/loopparallelism?rev=1239674779 text/html 2009-10-26T12:06:42-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/masterworker?rev=1256584002 A common problem in parallel programming is how to balance the computational load among a set of processing elements within a parallel computer. For task parallel programs with no communication between tasks (or infrequence but well-structured, anonymous communication) and effective solution with “automatic dynamic load balancing” is to define a single master to mange the collection of tasks and collect results. Then a set of workers grab a task, do the work, send the results back to the maste… text/html 2009-04-08T13:42:41-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/memory_parallelism?rev=1239223361 Bryan text/html 2009-04-08T15:41:26-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/memoryparallelism_comments?rev=1239230486 the name “memory parallelism” doesn't make sense. Or maybe it makes sense and I don't understand what the point of this pattern is. Parallelism built around the data in a problem is data parallelism. So I assume this pattern is about something else. I assume its about organizing a computation around the way memory is laid out in memory. text/html 2009-05-10T17:45:01-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/monte_carlo?rev=1242002701 Name Monte Carlo Methods Problem The solution to some problems can be estimated by statistical sampling its solution space with a set of experiments using different parameter settings. How do we efficiently construct and execute thousands to millions of experiments, analyze the results, and arrive at a solution? text/html 2009-03-17T21:28:59-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/monte_carlo_comments?rev=1237350539 Comments: Name: Problem: Context: Forces: Solution: Flow chart. <<<<<< the write up in the pattern is a bit weak in its discussion of parallel random number generators. I suggest the following text insted >>>> Random numbers are challenging for a parallel computation. First off, the period of the pseudo random number generator must be larger than the sequence used in the computation. Random number generators are parameterized and in a quality generator, the programmer can choose par… text/html 2009-04-08T13:40:54-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/mutual_exclusion?rev=1239223254 Jike text/html 2009-03-02T11:40:54-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/n-body_methods?rev=1236022854 Name N body methods Problem The problem involves updates to a system where each element of the system rigorously depends on the state of every other element of the system. How do we compute (or approximate) these updates in an efficient and scalable fashion? text/html 2009-05-05T13:04:21-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/non-work-efficient_parallelism?rev=1241553861 Name: Non-work-efficient Parallelism Problem: Many problems operates on a set of data by sequentially iterating over the data in particular sequences. There may not be any appearance parallelism in the sequential algorithm, however, if we are open to doing some redundant computation, parallel can be extracted. How do we extract this type of parallelism? text/html 2009-02-23T23:52:14-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/pattern1_0?rev=1235461934 [Our Pattern Language] (Pattern Language Glossary) (Pattern Template) (Pattern Workshop) (Pattern v1.0) (Pattern v2.0) Productivity Layer Applications Choose your high level architecture Guided Decomposition Choose your high level structure Task Decomp… text/html 2009-08-27T10:09:15-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/patternabstract?rev=1251392955 Structural Patterns Agent and Repository * The problem is expressed as a collection of independent tasks (i.e. autonomous agents) operating on a large data set (i.e. a central repository), * The solution involves efficiently managing all accesses by the agents while maintaining data consistency, a task can be the execution of an agent, or the operation where each agent is updating the repository. text/html 2009-02-18T14:56:14-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/patternlanguagecomments?rev=1234997774 Comments from February workshop: text/html 2009-11-15T14:51:48-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/patterns?rev=1258325508 Read me first! => [Our Pattern Language] (notes) (Glossary)(Blogs) (Pattern Template) (Pattern Abstract) (Pattern Workshop) (Pattern in Education) Applications Structural Patterns Computational Patterns Agent and Repository Pipe-and-filter Backtrack Branch and Bound (notes) Monte Carlo Methods(notes) Arbitrary Static Task Graph Process Control Circuits(notes) N-Body Methods Iterati… text/html 2009-09-23T13:17:55-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/patternsineducation?rev=1253737075 Berkeley: * CS267: Applications in Parallel Computing * CS294: Patterns in Computer Architecture text/html 2009-02-11T15:21:05-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/patterntemplate?rev=1234394465 [ Pattern Writing Checklist] Name: A noun phrase descriptive of the solution Problem: A simple statement of the problem being solved Context: Define context and background to understand the problem. After reading this section, a reader should know if this is the pattern to use. Ideally closes with a question to sum up the specific problem to be solved text/html 2009-11-16T23:37:52-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/patternworkshop?rev=1258443472 January Pattern Workshop Date: 01/27/2010 Time: 12noon - 3pm Location: Soda Hall 511, UC Berkeley 12noon - 1:00pm 1:00pm - 2:00pm Monte Carlo Pattern: Terry 2:10pm - 3:00pm November Pattern Workshop Date: 11/11/2009 Time: 1pm - 3pm text/html 2009-01-20T11:16:41-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/pipe-and-filter?rev=1232479001 Problem Many problems involve the application of a set of transformations to a stream of data. How do you support this type of problem with scalable solutions that non-specialists can program? Context Consider a stream of input data, which could be a stream signal received from the antenna, a flow of network packets, a segment of video, or a piece of computer program code. The goal is to apply a set of operations/computations (or filters) in a particular order (or partial order) to the inpu… text/html 2009-03-18T10:58:05-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/pipeline_comments?rev=1237399085 this pattern has the same name as a structural pattern found at a higher level. That bugs me. I wonder ... do we want to generalize this as “data flow”? Or should we just keep it as “pipeline”? or do we even need it at all at this level ... i.e. do we need it as a structural and an algorithm-strategy pattern? text/html 2009-11-23T12:43:38-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/process_control?rev=1259009018 Name Process Control Problem Many systems are intended to provide dynamic control of a physical environment using a feedback loop in which inputs are used by the system to determine a set of outputs that will produce a new state of the environment. text/html 2009-04-08T11:43:13-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/recursive_splitting?rev=1239216193 text/html 2009-04-15T00:10:09-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/recursive_splitting_comments?rev=1239779409 I liked the problem statement and the overall approach used in the solution section. The related patterns section near the end was Excellent! The context section needs some work. Remember, the goal is to layout the problem and guide the reader to the solution. You open nicelly with this approach, but then leap to discussing how this pattern relatest to the other patterns. I'd leave that content for your later related patterns section. text/html 2009-04-08T13:42:31-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/shared_data?rev=1239223351 Mark text/html 2009-05-05T14:01:30-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/shared_hash_table?rev=1241557290 Shared hash table: A hash table is one an important data structure in a wide range of problems. It is particularly important in parallel algorithms as a wide range of distributed data structures can be mapped onto a hash table. As with the distributed array pattern, the problem is the indexing required to transform a global hash key into a local hash key for a particular member of the set of processes or threads involved with a parallel computation. The solution is to place the indexing opera… text/html 2009-04-13T12:38:27-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/shared_queue?rev=1239651507 text/html 2009-11-10T15:21:52-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/simd?rev=1257895312 [SIMD] text/html 2009-02-10T14:25:03-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/sparse_linear_algebra?rev=1234304703 Name Sparse Linear Algebra Problem Some problems are defined in terms of linear operations over arrays of data (e.g. vectors and matrices) the elements of which are mostly zeros (sparse arrays). How do you optimize these operations to minimize storage and maximize performance? text/html 2008-12-29T08:37:29-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/spectral_methods?rev=1230568649 The original document was at It focuses only on the use of spectral methods in solving PDEs, i.e. in structured and unstructured meshes, but spectral methods are just as important in solving particle systems. Moreover, sometimes people just want to compute a FFT. text/html 2009-05-11T18:02:35-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/speculation?rev=1242090155 text/html 2009-10-26T12:07:20-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/spmd?rev=1256584040 Single-Program Multiple Data (SPMD): Keeping track of multiple streams of instructions can be very difficult for a programmer. If each instruction stream comes from independent source code, the software can quickly become unmanageable. There are a number of solutions to this problem. One is to have a single program (SP) that is used for all of the streams of instructions. An process/thread ID (or rank) is defined for each instance of the program and this can be used to index into multiple d… text/html 2009-10-26T12:06:17-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/strict-data-par?rev=1256583977 Data parallel algorithms constitute a large class of algorithms depending on the details of how data is shared as operations are applied concurrently to the data. If the sharing is minimal or if it can be handled by well-defined collective operations (e.g. parallel pre-fix or shift and mask operations) it may be possible to solve the problem with a single stream of instructions applied to data elements concurrently. In other words, the concurrency is strictly represented as a single stream of … text/html 2009-02-18T15:45:40-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/structured_grids_comments?rev=1235000740 Comments from February workshop: Name: Problem: Context: Forces: Solution: Invariants: Example: Known uses: Related patterns: References: Authors: text/html 2009-08-27T10:07:26-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/task_parallelism?rev=1251392846 Name: Task Parallelism Problem: We often describe a problem as a collection of tasks operating on data. When many of the tasks can be executed concurrently, how can we efficiently exploit the concurrency? Context: In the compute-centric view of a problem, we focus on defining a set of tasks that operates on data. The underlying assumption is that the problem is compute-intensive and the distribution of data working set is of secondary concern for performance. This assumption is often valid … text/html 2009-05-04T17:54:23-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/task_queue?rev=1241484863 Katya Tentative problem statement: In several applications the number of tasks generated for parallel execution is unknown, how do we efficiently manage the task scheduling among processing elements to guarantee load balance and locality? text/html 2009-04-24T16:33:36-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/taskparallelism_comments?rev=1240616016 Name: Problem: Compute-centric? an alternative to this phase? Context: Distinguish between this and pipeline algorithm strategy pattern Forces: Universal: Implementation forces: HW task queue Solution: Solution 1 and 2 in parallel. Invariants: Example: Known uses: Related patterns: References: Authors: text/html 2009-01-19T15:28:01-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/unstructured_grids?rev=1232407681 Name Unstructured Grid Problem Many problems can be described in the form of updates on an irregular mesh or grid: in other words, the space between mesh points in each dimension vary. Each mesh element is updated using neighboring mesh elements. How can we efficiently perform these computations? text/html 2009-02-18T15:38:29-08:00 http://parlab.eecs.berkeley.edu/wiki/patterns/unstructured_grids_comments?rev=1235000309 Comments from February workshop: Name: Problem: Context: Forces: Solution: Invariants: Example: Known uses: Related patterns: References: Authors: