-
Notifications
You must be signed in to change notification settings - Fork 0
Spec standard Issues List
This is a place to accumulate a list of design issues and our choices. When you fill in your proposals under each entry, please label it with your name and initials.
(KK) Proposal:
-
Don’t try to figure out what is the standard, what are restrictions and what are extensions. Rather, first focus on the set of possible features (semantics and syntax). Only after that should we sort them out.
-
Determine for each, the reasons we are even talking about it:
• Support for optimizations
• Support for error checking
• Functionality
• Ease of use
(VS) We should have a standardized textual representation of a CnC graph language from which "glue code" can be generated for different runtime systems
• Ease of use
• Support for optimizations
• Error checking
(VS) The graph language should include item collections and step collections, but not control tag collections. (There is no* loss of generality in excluding tag collections.) The prescribe relationship should be specified directly between pairs of step collections as in the Reduced CnC proposal. The possible edges in the graph are as follows: (Step1)-->[Item2] // put operation [Item2]-->(Step3) // get operation (Step1)::(Step2) // prescribe operation
(FS) prescribing steps by steps could be optional. Not having tag-collections removes the valuable mediator between controller and controllee and only leaves a mediator for data. Tag-collections allows cleaner and more flexible SW engineering.
(VS) Also consider the possibility of including a step join operation, (Step1)-->(Step3), which serves as an explicit synchronization between steps. It should not be needed if users follow a pure CnC model of only accessing sharing data in item collections, but is useful when users would like steps to share other data structures that are not in item collections.
(FS) Using shared but not item-collected data could be optional, but should also require being marked explicitly because it limits (or removes) CnC's nice property of being independent of the memory model.
• Ease of use
• Optimizaitons (harder)
• Error checking (harder)
(VS) All step inputs should be independent i.e., the tag/key for a get operation should only depend on the step's control tag, and not on the value of another get operation. There is no loss of generality with this restriction.
• Ease of use (harder)
• Optimization
(FS) Do we want the same for put operations? Would be good for tag-function analysis. Would it restrict generality?
• Optimization
• Restrict functionality
(VS) It is desirable for a "caller step" to pass additional parameters by value to a "callee step" that it prescribes. The control tag is the only required parameter (like a primary key), whereas additional parameters are optional.
(FS) What's the difference between such a parameter and a tag-component? Is it only that it might not be used in tag-functions?
• Ease of use
(VS) The graph language should require the specification of "tag functions" for get operations i.e., the name of a user-defined function that can be used to compute the tag/key for a get operation as a function of the step's control tag. As an option, we can also support a simple expression syntax that the user can use to specify tag functions directly in the graph language. But they should always have the ability to define a tag function in the host language.
(FS) If we allow variants, it seems natural to start with a generic base-language and let variants be more restricted. Requiring tag-functions in the base-language does the opposite (accounting for the fact that we already have variants which do not require tag-functions).
(FS) Using user-provided functions raises portability issues. A definition of some kind of API/ABI for every "supported" target-language would be nice.
• Optimization
• Ease of use (harder)
(VS) We should discuss adding support for user-defined reductions to the CnC base language. Two proposals from past work can be found in the following papers:
Deterministic Reductions in an Asynchronous Parallel Language. Zoran Budimlic, Michael Burke, Kathleen Knobe, Ryan Newton, David Peixotto, Vivek Sarkar, Edwin Westbrook. The 2nd Workshop on Determinism and Correctness in Parallel Programming (WoDet), March 2011.
CnC-Hadoop: a Graphical Coordination Language for Distributed Multiscale Parallelism. Riyaz Haque, David M Peixotto, Vivek Sarkar. ACM Computing Frontiers 2011.
• Functionality
• Ease of use
• Optimization
(VS) This should not be required, but a user should optionally be able to specify tag functions for put operations i.e., the name of a user-defined function that can be used to compute the tag/key for a put operation as a function of the step's control tag. The availability (and analyzability) of these tag functions can enable important memory optimizations. As an example, see the following reference:
Declarative Aspects of Memory Management in the Concurrent Collections Parallel Programming Model. Zoran Budimlic, Aparna Chandramowlishwaran, Kathleen Knobe, Goeff Lowney, Vivek Sarkar, Leo Treggiari. Proceedings of DAMP 2009 Workshop (Declarative Aspects of Multicore Programming), co-located with POPL, January 2009.
• Optimization
(VS) This should not be required, but a user should optionally be able to specify specify "get-count" functions for put operations. As an example, see the following reference:
Folding of Tagged Single Assignment Values for Memory-Efficient Parallelism. Dragos Sbirlea, Kathleen Knobe, Vivek Sarkar. International European Conference on Parallel and Distributed Computing (Euro-Par), August 2012.
• Optimization
(VS) This should not be required, but a user should optionally be able to specify specify folding functions for data items. As an example, see the Euro-Par 2012 paper referenced above.
• Optimization
(VS) Controlled nondeterminism can be added to the CnC model with the putIfAbsent operation. Should we consider this as an optional feature of the base language?
(KK) I do like the idea of allowing some nondeterminism as long as it's explicit in the graph, not just the step code. The putIfAbsent worked will for the problem of embedding a tree in a graph. But we should consider the problem more broadly. The putIfAbsent looks at the current runtime state. There are other aspects of the state we might consider. One example is getIfPresent. This would allow for a step to proceed with or without a given input. More globally, maybe the graph specifies the general computation but for this run we want the first 10 items produced. I'm just proposing non-determinism that depends on the current execution state, not arbitrary non-determinism. That would be a different topic.
• Functionality
(VS) We should define a tuning language separately from the base graph language. This can come later, but it's important to consider what requirements the tuning language will impose on the base graph language.
• Optimization
(KK) Is a disconnected graph legal? Is a graph with a step that doesn't produce either tags or items legal?
• Error checking
(KK) Are data-dependent gets allowed? Are data-dependent puts allowed? There are 4 possible kinds of tag function. Do we allow/require
item-produced-by item-consumed-by step-consumes step-produces
• Optimization
• Error checking
(KK) is the syntax: (foo), [x], or foo( ), x[ ], myTag< > ?
• Ease of use
(KK)
• Ease of use
• Optimization
(KK)
(FS) Scoping and naming/mapping issues
(FS) tag-space slicing and/or sub-/super-typing
• Ease of use
(FS) It should support tags and items of any type. Supporting a simple expression syntax might require something like a type declaration capability.
• Ease of use
(KK) support multiple implementation of a given step together with some decision procedure.
• Optimization
(KK) This is a non-deterministic feature. A step can perform a computation that and determine that some other step should not run even if its tag is produced. Obviously this will have no result if the step is already complete and it would apply if the step tag has been produced but the step hasn't started. What if the step has started?
• Functionality
(FS) It should be possible to provide implementation specific hints, options, etc.
• not sure what category this is