[kepler-dev] extending kepler with workflow optimization algorithms

Thu Jul 7 17:01:19 PDT 2011

Hi Efthymia,
Scheduling of actor models is a deep topic.
Kepler uses Ptolemy II as its execution engine.
Ptolemy II is based on Ptolemy Classic.
In Ptolemy Classic, we had a number of different synchronous dataflow scheduling
algorithms, many of these were oriented towards clustering for parallel
processing.

In your example model, I see there being two costs:
1) The cost of the service.  For example FICO might charge more money
per query than an email lookup service.
2) The number of tokens passed between actors varies.

There is a relationship between these two costs where #1 is usually the
more important cost, but #2 can eventually overrule #1.

Offhand, I don't know of a model of computation that does exactly what
you want.

In Ptolemy II, models like your example model are typically Kahn
Process Network (PN) models where each actor is a separate process.

http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/ptolemy/domains/pn/doc/
says:

   "The following are the most important features of the operational semantics of
   PN as proposed by Kahn and MacQueen:

   * This is a network of sequential processes.
   * The processes do not share memory. Instead they communicate with each other
   only through unidirectional FIFO channels.
   * Communication between processes is asynchronous.
   * Processes block on a read from a FIFO channel if the channel is empty but
   can write to a channel whenever they want to."

In PN, there is not really a predefined schedule, the threads operate and then block.

Synchronous Dataflow (SDF) can be thought of as a subset of PN, where
the number of tokens is known in advance and a schedule is defined in advance.

Dynamic Dataflow (DDF) is between the two, where the number of tokens passed
between actors is not known in advance.

There is another trivial director called the LeftToRightDirector that fires the actors
in order from LeftToRight.  This would allow you to drag actors around and try
different firings.  That director is at
ptII/doc/tutorial/domains/LeftRightDirector.java

http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIfaq.htm#kepler
says
"If you want to use a director not in Kepler tree, you have to use the "Tools/Instantiate Attribute" menu. I use it to get a DDF director frequently (class ptolemy.domains.ddf.kernel.DDFDirector). "

So, in Kepler, you would do Tools-> Instantiate Attribute and then
enter doc.tutorial.domains.LeftRightDirector, but that does
not seem to work in Kepler, so you would need to download Ptolemy II via
http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/

The Timed Multitasking model (TM) is somewhat close to what you want
http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/ptolemy/domains/tm/doc/
says
--start--
The timed multitasking (TM) domain, created by Jie Liu, offers a model of computation based on priority-driven multitasking, as common in real-time operating systems (RTOSs), but with more 
deterministic behavior. In TM, actors (conceptually) execute as concurrent threads in reaction to inputs. The domain provides an event dispatcher, which maintains a prioritized event queue. The 
execution of an actor is triggered by the event dispatcher by invoking first its prefire() method. The actor may begin execution of a concurrent thread at this time. Some time later, the dispatcher 
will invoke the fire() and postfire() methods of the actor (unless prefire() returns false).

The amount of time that elapses between the invocation of prefire() and fire() depends on the declared /executionTime/ and /priority/ of the actor (or more specifically, of the port of the port 
receiving the triggering event). The domain assumes there is a single resource, the CPU, shared by the execution of all actors. At one particular time, only one of the actors can get the resource and 
execute. Execution of one actor may be preempted by another eligible actor with a higher priority input event. If an actor is not preempted, then the amount of time that elapses between prefire() and 
fire() equals the declared. /executionTime/. If it is preempted, then it equals the sum of the /executionTime/ and the execution times of the actors that preempt it. The model of computation is more 
deterministic than the usual priority-driven multitasking because the actor produces outputs (in its fire() method) only after it has been assured access to the CPU for its declared /executionTime/. 
In this domain, the model time may be synchronized to real time or not.

--end--

For an overview of the models of computation, see the "Domain Overview" link at
the top of
http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/doc/index.htm

or the first chapter of

      http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-28.pdf

_Christopher

On 7/7/11 2:10 AM, Efthymia Tsamoura wrote:
> Hello
>
> I am a phd student and during this period i am dealing with workflow optimization problems in distributed environments.  I would like to ask, if there are exist any cases where if the order of task 
> invocation in a scientific workflow changes its performance changes too without, however, affecting the produced results. In the following, a present a small use case of the problem i am interested in:
>
> Suppose that a company wants to obtain a list of email addresses of potential customers selecting only those who have a good payment history for at least one card and a credit rating above some 
> threshold. The company has the right to use the following web services
>
> WS1 : SSN id (ssn, threshold) -> credit rating (cr)
> WS2 : SSN id (ssn) -> credit card numbers (ccn)
> WS3 : card number (ccn, good) -> good history (gph)
> WS4 : SSN id (ssn) -> email addresses (ea)
>
> The input data containing customer identifiers (ssn) and other relevant information is stored in a local data resource. Two possible web service linear workflows that can be formed to process the 
> input data using the above services are C1 = WS2,WS3,WS1,WS4 and C2 = WS1,WS2,WS3,WS4. In the first workflow, first, the customers having a good payment history are initially selected (WS2,WS3), and 
> then, the remaining customers whose credit history is below some threshold are filtered out (through WS1). The C2 workflow performs the same tasks in a reverse order. The above linear workflows may 
> have different performance; if WS3 filters out more data than WS1, then it will be more beneficial to invoke WS3 before WS1 in order for the subsequent web services in the workflow to process less 
> data.
>
> It would be very useful to know if there exist similar scientific workflow examples (where the order of task invocation can change and it is not known a-priori by the user, while the workflow 
> performance depends on the workflow task invocation order) and if you are interested in extending kepler with optimization algorithms for such workflows.
>
> I am asking because i have recently developed an optimization algorithm for this problem and i would like to test its performance in a real-world workflow management system with real-world workflows.
>
> P.S.: references to publications or any other information dealing with scientific workflows of the above rationale will be extremely useful.
>
> Thank you very much for your time
>
>
>
> _______________________________________________
> Kepler-dev mailing list
> Kepler-dev at kepler-project.org
> http://lists.nceas.ucsb.edu/kepler/mailman/listinfo/kepler-dev

-- 
Christopher Brooks, PMP                       University of California
CHESS Executive Director                      US Mail: 337 Cory Hall
Programmer/Analyst CHESS/Ptolemy/Trust        Berkeley, CA 94720-1774
ph: 510.643.9841      	                      (Office: 545Q Cory)
home: (F-Tu) 707.665.0131 cell: 707.332.0670

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.nceas.ucsb.edu/kepler/pipermail/kepler-dev/attachments/20110707/e631cf96/attachment-0001.html>