<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Hi Efthymia,<br>
Scheduling of actor models is a deep topic.<br>
Kepler uses Ptolemy II as its execution engine.<br>
Ptolemy II is based on Ptolemy Classic.<br>
In Ptolemy Classic, we had a number of different synchronous
dataflow scheduling<br>
algorithms, many of these were oriented towards clustering for
parallel <br>
processing.<br>
<br>
In your example model, I see there being two costs:<br>
1) The cost of the service. For example FICO might charge more
money<br>
per query than an email lookup service.<br>
2) The number of tokens passed between actors varies. <br>
<br>
There is a relationship between these two costs where #1 is usually
the<br>
more important cost, but #2 can eventually overrule #1.<br>
<br>
Offhand, I don't know of a model of computation that does exactly
what<br>
you want.<br>
<br>
In Ptolemy II, models like your example model are typically Kahn<br>
Process Network (PN) models where each actor is a separate process.<br>
<br>
<a class="moz-txt-link-freetext" href="http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/ptolemy/domains/pn/doc/">http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/ptolemy/domains/pn/doc/</a><br>
says:<br>
<br>
"The following are the most important features of the operational
semantics of<br>
PN as proposed by Kahn and MacQueen:<br>
<br>
* This is a network of sequential processes.<br>
* The processes do not share memory. Instead they communicate with
each other<br>
only through unidirectional FIFO channels.<br>
* Communication between processes is asynchronous.<br>
* Processes block on a read from a FIFO channel if the channel is
empty but<br>
can write to a channel whenever they want to."<br>
<br>
In PN, there is not really a predefined schedule, the threads
operate and then block.<br>
<br>
Synchronous Dataflow (SDF) can be thought of as a subset of PN,
where<br>
the number of tokens is known in advance and a schedule is defined
in advance.<br>
<br>
Dynamic Dataflow (DDF) is between the two, where the number of
tokens passed<br>
between actors is not known in advance.<br>
<br>
There is another trivial director called the LeftToRightDirector
that fires the actors<br>
in order from LeftToRight. This would allow you to drag actors
around and try<br>
different firings. That director is at<br>
ptII/doc/tutorial/domains/LeftRightDirector.java<br>
<br>
<a class="moz-txt-link-freetext" href="http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIfaq.htm#kepler">http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIfaq.htm#kepler</a><br>
says<br>
"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). "<br>
<br>
So, in Kepler, you would do Tools-> Instantiate Attribute and
then<br>
enter doc.tutorial.domains.LeftRightDirector, but that does<br>
not seem to work in Kepler, so you would need to download Ptolemy II
via<br>
<a class="moz-txt-link-freetext" href="http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/">http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/</a><br>
<br>
The Timed Multitasking model (TM) is somewhat close to what you want<br>
<a class="moz-txt-link-freetext" href="http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/ptolemy/domains/tm/doc/">http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/ptolemy/domains/tm/doc/</a><br>
says<br>
--start--<br>
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).
<p>The amount of time that elapses between the invocation of
prefire() and
fire() depends on the declared <i>executionTime</i> and <i>priority</i>
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.
<i>executionTime</i>. If it is preempted, then it equals the sum
of the
<i>executionTime</i> 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 <i>executionTime</i>. In this domain, the model time may
be
synchronized to real time or not.<br>
</p>
<p>--end--<br>
</p>
<br>
<br>
For an overview of the models of computation, see the "Domain
Overview" link at <br>
the top of<br>
<a class="moz-txt-link-freetext" href="http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/doc/index.htm">http://ptolemy.eecs.berkeley.edu/ptolemyII/ptII8.0/ptII8.0.1/doc/index.htm</a><br>
<br>
or the first chapter of<br>
<h3><a
href="http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-28.pdf">http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-28.pdf</a></h3>
<br>
_Christopher<br>
<br>
<br>
<br>
<br>
<br>
<br>
On 7/7/11 2:10 AM, Efthymia Tsamoura wrote:
<blockquote
cite="mid:20110707121030.20676y8v5u1t7bpi@webmail.auth.gr"
type="cite">Hello
<br>
<br>
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:
<br>
<br>
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
<br>
<br>
WS1 : SSN id (ssn, threshold) -> credit rating (cr)
<br>
WS2 : SSN id (ssn) -> credit card numbers (ccn)
<br>
WS3 : card number (ccn, good) -> good history (gph)
<br>
WS4 : SSN id (ssn) -> email addresses (ea)
<br>
<br>
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.
<br>
<br>
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.
<br>
<br>
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.
<br>
<br>
P.S.: references to publications or any other information dealing
with scientific workflows of the above rationale will be extremely
useful.
<br>
<br>
Thank you very much for your time
<br>
<br>
<br>
<br>
_______________________________________________
<br>
Kepler-dev mailing list
<br>
<a class="moz-txt-link-abbreviated" href="mailto:Kepler-dev@kepler-project.org">Kepler-dev@kepler-project.org</a>
<br>
<a class="moz-txt-link-freetext" href="http://lists.nceas.ucsb.edu/kepler/mailman/listinfo/kepler-dev">http://lists.nceas.ucsb.edu/kepler/mailman/listinfo/kepler-dev</a>
<br>
</blockquote>
<br>
<pre class="moz-signature" cols="200">--
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
</pre>
</body>
</html>