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
[email protected]
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
