Patrick Kimani
email: patrick.kimani@gccaz.edu

Laura Watkins
email: laura.watkins@gccaz.edu

April Ström
email: april.strom@cgc.edu

Irene Duranczyk

Vilma Mesa
email: vmesa@umich.edu

Inah Ko
email: inahko@umich.edu

Ai @ Cc

Megan Breit

Engaging community colleges faculty in developing items for assessing mathematical knowledge for teaching

Keywords: Mathematical knowledge for teaching, tasks of teaching, choosing problems, understanding student's work, student thinking

In this paper we investigate how experienced community college mathematics faculty, taking part in an item-writing camp designed to generate items to assess mathematical knowledge for teaching college algebra, thought about student thinking and the work of teaching in this context. We conceived of the participants' knowledge as practice-based professional learning. By analyzing video records of item development sessions, drafts of items produced, feedback sessions on the items, and selfreports of their learning during the camp, we identified four major themes related to participants' work highlighting the possible advantages of engaging faculty in item-writing: understanding mathematical knowledge for teaching, understand the item writing process, drawing on their teaching experience in the item-writing process, and noticing the complexity of writing MKT items. These themes make salient the advantages of engaging classroom-based faculty in item-writing.

Introduction

Over the last two decades, researchers have attempted to identify and describe the relationship between teacher mathematical knowledge for teaching and student achievement [START_REF] Hill | Effects of teachers' mathematical knowledge for teaching on student achievement[END_REF]. Several research groups have developed instruments for measuring this special type of knowledge targeting specific grade bands (e.g., [START_REF] Hill | Developing measures of teachers' mathematics knowledge for teaching[END_REF]. To develop items that reliably assess this type of teacher knowledge researchers have collaborated with mathematicians and practitioners (teachers, teacher educators, and professional developers), so that both the mathematics at stake and the ways in which it manifests in the classroom are authentically represented in the items. Relevant grade-level teachers have taken part in cognitive interviews, instrument piloting, or assessment item-writing camps [START_REF] Phelps | Developing content knowledge for teaching assessments for the Measures of Effective Teaching Study[END_REF]. Selling and colleagues (2016) have argued that item developers need support to make sense of the nuances of the knowledge construct and the best ways to assess it, yet there is little documentation about how classroom-based faculty work in collaboration with mathematical knowledge for teaching (MKT, Hill, Schilling, & Ball, 2004) researchers to create items for MKT instruments, or about their thinking process as they generate ideas and contribute to the item-writing process. This paper presents an exploration of how a group of 13 practitioners (community college mathematics faculty who teach college algebra), chosen from different regions of the United States, thought about their students' thinking, in the context of a twoweek item-writing camp in which they were asked to produce 10 different multiple choice or testlet MKT items each. Involving teaching faculty in writing MKT items is not typically done by other MKT-assessment instrument developers-those groups limit practitioner input to feedback through cognitive interviews and pilot studies. We set out to answer this research question: In what ways does leveraging hypothetical examples of student work facilitate the development of MKT items designed to measure instructors' knowledge of students' mathematical reasoning?

The participants were invited as part of a large project that seeks to develop an assessment for mathematical knowledge for teaching college algebra at U.S. community colleges. College algebra is a credit-bearing course taught in postsecondary institutions in the United States, and typically covers content related to linear, rational, and exponential functions, as well as other relevant algebraic concepts in preparation for calculus. The number of students taking this course at U.S community colleges has steadily increased from about 190,000 in 2000 to about 300,000 in 2015 (Conference Board of the Mathematical Sciences, 2015). This course is considered a gateway to degrees in science, technology, engineering, and mathematics (STEM), being a prerequisite for a STEM calculus sequence. The immense number of students who take this course at U.S. community colleges, and consequently the large number of teachers needed to fill this need, creates an opportunity for developing an instrument that assesses the MKT of community college faculty teaching college algebra, (MKT-CCA), in these institutions; such instrument can serve as a tool for understanding the quality of instruction of this key course and its impact on student learning.

Sustained prior work to corroborate that MKT is composed of the various dimensions identified in the literature (e.g., subject matter knowledge, pedagogical content knowledge, [START_REF] Shulman | Those who understand: Knowledge growth in teaching[END_REF]) has proven very difficult. We chose follow [START_REF] Ko | Subject matter knowledge of geometry needed in tasks of teaching: Relationship to prior geometry teaching experience[END_REF] who successfully distinguished knowledge needed when geometry teachers perform two different tasks of teaching, understanding student work and choosing problems. Tasks of teaching are the "recurrent practices that make up the work of teaching [school] subjects" (Phelps, et al., 2014, p. 3). Since these tasks of teaching are indeed foundational for teachers' work and given that there is evidence that it is possible to identify two distinct types of knowledge, we chose this conceptualization to develop our instrument. We used a tasks of teaching framework and adopted a two-dimensional hypothesis for the construct: (1) choosing problems and (2) understanding student work. We hypothesize that the knowledge that community college instructors use to choose problems for teaching college algebra can be distinguished from the knowledge that they use to understand students' work in college algebra. We (four university researchers, four community college faculty-researchers, three graduate students) developed a pool of items after training in instrument development. After developing a set of principles for writing items we invited practitioners to develop items along these two dimensions.

Methods

We recruited 13 community college faculty to participate in a two-week item-writing camp. These practitioners came from different geographical regions, taught at different types of colleges (urban, suburban, large, small), had varied demographic characteristics (e.g., race, gender), and had some experience writing cognitive tests and working collaboratively in small groups. These criteria generated a diverse group and shortened the time needed for training and team building. During the virtual item-writing camp we provided training for the participants that included: (1) an introduction to MKT literature, (2) definitions of the two tasks of teaching, ( 3) examples of items from our item pool, and ( 4) ways of checking that items fit the definition of the task of teaching they were targeting. We also provided a set of algebra topics we selected as representative of core mathematical ideas in college algebra, and that relate to linear, rational, and exponential functions. The faculty worked in self-selected teams of 2 to 3 participants; they were asked to draft items with feedback being provided by other participants and members of the research team in several cycles of feedback and revision.

Data and analysis

We collected two types of data (1) audio and video recorded work sessions in which the faculty worked collaboratively in teams to draft items, reviewed draft items from other teams, and used other teams' review comments to change and improve their drafts, and (2) reflection memos from the 13 instructors written at the end of each week, and that sought personal insights on the work of writing items. We used both ongoing and retrospective analyses of the data. Ongoing analysis occurred during the item-writing camp and involved reviewing the reflection memos after Week 1 to identify common themes using an open coding and a constant comparative method [START_REF] Corbin | Basics of qualitative research[END_REF]. These themes informed prompts for the reflection memo delivered after Week 2. Figure 1 shows one of the themes, its subthemes, and sample quotes that emerged. During retrospective analysis, we examined all available data (recordings and memo responses) using the coding system used to analyze the reflection memos from Week 1 while adding new themes and sub themes as needed. Four researchers independently coded these records; then met to compare, discuss, and agree on a final list of themes identified across the data set. This paper presents preliminary findings focusing on the data found in participants' memos.

Preliminary Findings

Four themes emerged from our data related to the participants': (a) attempts to understand MKT, (b) attempts to understand the MKT-item writing process, (c) attempts to draw on their teaching experience in the item-writing process, and (d) realizations of the complexity of writing MKT items.

The first two themes were not entirely surprising, as they represent issues that anyone doing the work of MKT instrument development has to grapple with. Due to space limitations, we present findings about the last two themes to highlight insights into experiences of MKT writers who were encountering MKT research for the first time. These themes represent ways in which participants wrestled with writing items to assess community college instructors' thinking about student thinking.

Drawing on Teaching Experience

Participants leveraged their teaching experience in the item-writing process in two different ways: (a) They used common student errors that they have observed in their own teaching of college algebra and (b) negotiating the goals of the college algebra course impacted their decisions in item writing.

Using Common Student Errors. Of the 13 instructors, ten reflected on how they sought to use common student errors they have encountered in their experience teaching college algebra to write items that would assess community college instructors' thinking about student thinking. They wrote that they began with common "mistakes," "errors," or "misconceptions" that they see in their own teaching. For example, Steph (pseudonym) wrote:

I thought about problematic areas… common (from my experience) struggles [students] face or challenges they have in making sense of the ideas… like percent, geometric mean, ... then I created a couple of items to assess an instructor's ability to connect their math content knowledge with these hypothetical student responses. (Steph, Memo# 2, June 10, 2021).

Steph gave Figure 2 as an example of an item he created by reflecting on his knowledge of students' thinking. His ability to reflect on a common student struggle informed his decision to draft a realistic problem for college algebra at community colleges. Participant's knowledge of students' struggles with mathematical ideas was valuable for the item development process.

Negotiating Goals for College Algebra. Our analysis revealed that participants leveraged their teaching experience as they wrote items to assess instructors' ability to interpret students' work relative to the instructional goals for the course. For example, Taylor wrote about the importance of writing items that focus on community college instructors' ability to understand their students' conceptual and procedural understanding:

I tried to think about common errors or misconceptions I observe students making consistently... I also try to go back and forth between procedural and conceptual knowledge. Having procedural knowledge doesn't guarantee having conceptual understanding but it was difficult sometimes to pull and separate the two… I think that some of my items were focused on procedural knowledge more so than conceptual knowledge although having conceptual knowledge is key. (Taylor, Memo #2, June 10, 2021).

Taylor's understanding about the goals for college algebra enabled her to be mindful of the different types of understanding that the course seeks to develop, and to then think about the types of items needed to assess instructors' thinking about these types of student understandings. Trent also seemed to be thinking about the goals for this course when he wrote:

There Trent's comment highlights a challenge related to intended outcomes for college algebra as there is variation in course outcomes for college algebra across institutions and states. Trent's statement seemed to go a step further than Taylor's by thinking about how other participants in the item camp were thinking about teachers' thinking about student thinking. Professional teacher organizations in the U.S. encourage mathematics teachers at all levels to strike a balance between developing their students' conceptual understanding and procedural fluency (e.g., American Mathematical Association of Two-Year Colleges 2018). The challenge of making sense of a students' depth of understanding using a snapshot of a student's work presented on an MKT-CCA item in the absence of a dialogue with the student complicated the ability of item camp participants to write items that would assess an instructors' ability to think about and make judgements about student thinking. The participants' insights about the varying goals of college algebra contributed to the item-writing process in terms of the development of MKT-CCA items that assess test takers' ability to think about students' understanding in both procedural and conceptual terms.

Realizations of the Complexity of Writing MKT Items

Our data showed participants negotiating the complexity of writing MKT assessment items in three ways: (a) creating multiple-choice options that could be evaluated objectively, (b) evaluating evidence of students' understanding, and (c) the challenge of metacognition.

Creating multiple-choice options. Not only did the participants have to contend with crafting an item stem about an identified common student error but they also had to create either multiple-choice options or binary options for testlets that would be realistic for the stem and for college algebra. Eight participants wrote about their struggles with writing multiple-choice options. They gave varying reasons for why they struggled including: writing options that could be evaluated without subjectivity, writing realistic incorrect student responses, and using snapshots of students' incorrect work produces some unpredictability since students' work cannot be easily explained or packaged into a multiplechoice item. For example, Steph said:

Multiple choice questions are VERY hard to write. Do the MC choices have to be right or wrong? Or can they all be viable and the response will tell us something about the respondent? In my first case, correct student work is shown and the respondent is asked which question they might ask to follow up on student thinking. It might be argued that all 4 questions (MC options) are possible (that is... not really "wrong" or "right"...) (Steph, Memo #1, June 4, 2021)

Like Steph, most participants struggled to decide on how to orient multiple-choice options to best assess a test taker's understanding of students' work or the test taker's perceptions of the best way a teacher would respond to help a student struggling with a math concept. The latter was further exacerbated by test takers' perceptions of the goals of college algebra and how it should be taughttwo instructors could select diverging paths of intervention (e.g., two different follow up tasks) they believe would be appropriate intervention depending on their believes about teaching mathematics.

Evidence of student thinking. Ten participants wrote about the challenge of using students' written work and how that made writing items assessing community college instructors' ability to understand students' work difficult. Of the ten, five wrote about the difficulty of moving from a common student error to an MKT-CCA item, as illustrated in the following excerpt from Star's reflection memo:

Nearly all of my items were drawn from actual work that my students have done in the past. I found that more often than not, the mistakes that students make cannot easily be explained/do not follow a predictable pattern. While it made it very difficult to write options for those stems, I think those will be the most valuable for testing MKT! Writing the "Understanding" items was an interesting experience because it highlighted the assumptions we make about student work. What evidence do we base those assumptions on? Or is it all experience? (Star, Memo #2, June 10, 2021).

Star's pondering about the challenge of writing items about students' work, that different test takers who bring different teaching experiences, can interpret in a way that leads them to choose the same correct choice without the option of asking the student follow-up questions was shared by other participants. The jump from identifying common student errors to crafting an item that would meaningfully assess a community college instructor's thinking about the student's thinking posed challenges that Star and other participants had never wrestled with.

The Challenge of Metacognition. The reflection questions prompted participants to make explicit not only their thinking about their knowledge for teaching college algebra but to also think about the test takers' thinking about students' thinking and how that thinking would elicit knowledge needed in the particular task of teaching. The difficulty item writers had in thinking about student thinking suggests that the activity is not standard practice among community college instructors, that is, thinking about other faculty's knowledge is not in the scope of community college instructors' role as teachers, and we hypothesize that it is therefore rare. Star said:

The line between knowledge of college algebra and knowledge for teaching college algebra is much finer than I thought. My first pass at a lot of the items I wrote ended up testing the participant's [mathematical] knowledge, rather than their knowledge for teaching. I think a lot of my knowledge for teaching college algebra is subconscious, and I still haven't quite figured out what the difference is, in explicit terms. (Star, Memo #2, June 10, 2021).

Star's reflection suggests that the work of writing MKT items is different from the work of writing assessment items for students that focus on college algebra content. MKT items, especially those focused on understanding students' work are inherently different in the sense that they target to assess a test taker's mathematical thinking about students' thinking. Maggie touched on this in her memo:

The writing of the items is also new for me. It feels very meta to write not just what student thinking might be but to take it to the level of what a teacher might be thinking about student thinking and how student thinking can be elicited. Putting that into parallel foils is hard. Heck, writing the stem is hard! (Maggie, Memo #1, June 4, 2021)

Discussion

Involving practitioners in item writing meant adding a layer of training-as this was a group not intimately engaged in researching MKT-but also brought valuable perspectives to our item-writing process. Practitioners' experiences teaching college algebra at community colleges and their understanding of linear, rational, and exponential functions helped to enrich our database of items. Further, their ability to draw on their experiences to highlight common student errors for students in the targeted college algebra topics and their reflections on the goals for the course impacted the types of MKT-CCA items they drafted, which we believe will add to the diversity of items in the instrument. Finally, we found that the process of writing MKT-CCA items to assess instructors' thinking about student thinking provided the instructors who attended the item camp valuable insights into their own practice. Analysis of the data offered clues about how participants wrestled with issues such as what it means for a student to understand an idea and the kind of evidence needed to show understanding. The discussions held among partners in the item writing or reviewing process were rich and allowed the writers to think about issues around instruction that they do not ordinarily think about outside the context of thinking about a colleagues' thinking about student thinking.

Theme:Figure 1 :

 1 Figure 1: Sample theme, subthemes, and sample quotes

  is still a large divide between what different [other participants] think is most important in college algebra. My team is very much focused on conceptual understanding and big ideas and others appear to still hang on to what I personally think are outdated aspects of the course. (Trent, Memo #2, June 10, 2021).

Acknowledgment

Funding for this work was provided by the National Science Foundation (ECR awards 20006021, 20006442, 20005273, 20005664). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. We thank our participants; without them this work would not have been possible.


Marius Bozga
email: bozga@imag.fr

Abdelkarim Kerbaa
email: kerbaa@imag.fr

Oded Maler Verimag

Scheduling Acyclic Branching Programs on Parallel Machines *

In this paper we address the following problem: given an acyclic program scheme with if-then-else control structures, together with the duration of each procedure, and given an architecture consisting of n identical processors, compute offline a scheduling policy that will guarantee minimal execution time (in the worst-case) for the entire program on this architecture. Since this is a problem of scheduling under uncertainty (the results of the branching decisions are not known in advance) it cannot be solved in a satisfactory manner using static or fixed priority schedulers but rather requires a state-dependent scheduling strategy. We use timed automata technology to derive such strategies using algorithms for finding shortest paths on game graphs.

Motivation

The class of real-time applications that motivates this work consists of systems that interact with a physical environment and that have to perform computation based on sensory inputs that arrive on a periodic basis. Typical application domains include signal processing, such as radar, and realization of control loops in avionic and automotive domains. The philosophy underlying the development of such systems is a bit different from that used in the "operating systems" genre of real-time systems research.

To begin with, and in contrast with other approaches where the computations to be performed are modeled as independent tasks, whose only interaction is via conflicting demands for resources, we view tasks as admitting interrelationships such as precedence and conditional dependency. For example, various control tasks may need to wait for the results of some filtering algorithm before being executed and, moreover, different outcomes of the algorithm may invoke different follow-up computations. Secondly, unlike interactive systems, the major occupation of the class of systems we consider is with periodic, rather than aperiodic, computations. Finally such systems typically avoid the scheduling services of real-time operating systems, albeit their potential performance amelioration. This is partly due to historic reasons and partly because in safety-critical applications, being predictable with respect to timing is considered important while dynamic scheduling policies are perceived as risky and hard to validate. The main goal of this paper is to introduce a scheduling methodology which is appropriate for this type of applications (other efforts in this direction have been made within the time-triggered architecture [START_REF] Kopetz | The Time-Triggered Architecture[END_REF]).

To explain better our point of departure, let us focus on the development process of control programs written using the synchronous data-flow language Lustre, a special-purpose language tailored for control applications [START_REF] Halbwachs | The Synchronous Dataflow Programming Language LUSTRE[END_REF]. Lustre underlies the commercial programming environment SCADE, used for writing parts of the control loops of the Airbus. The philosophy of Lustre is quite simple. Instead of programming by hand the various tasks that realize the control loops, and delegating the handling of their invocation and inter-dependencies to a real-time operating system, the whole application is written in a uniform and modular data-flow style which resembles the block diagrams used by control engineers. In fact, Lustre is very similar to the discrete-time subset of Simulink and an automatic translator from Simulink to C via Lustre has been introduced recently [CCM + 03]. During compilation this high-level description is transformed into a single C program that runs on the target machine, with a minimal intervention of an operating system (only I/O and real-time clock services are needed). The advantage of this approach is summarized by the the slogan "what you compile is what you execute": the whole operational semantics resides inside the program itself rather than being shared with some third-party software with an obscure semantics.

The Lustre compiler generates a single loop C code without too much effort to optimize execution time using scheduling. While this is not such a big issue in critical systems such as in avionics, where the the total computation time of the control loop does not exceed the platform capabilities, other domains which are more computationally expensive (signal processing) or that use cheaper execution platforms (automotive, consumer electronics) require more aggressive scheduling without compromising semantic clarity.

As a starting point we consider an acyclic program which has to be invoked periodically and perform some set of inter-related tasks. We want to minimize the execution time of this program assuming an execution platform with a given number of identical processors. Finding this minimum allows us to determine the highest frequency in which the program can be executed. In real-time systems the problem is sometimes posed in a slightly different form where the frequency is specified (typically using "deadline" and "release time" constraints) and a schedule is sought that satisfies these constraints. Since in our search-based approach there is not much difference between optimization and constraint satisfaction problems, we prefer to concentrate on the former which is more generic. As the reader will see, adding constraints to our approach will only reduce the degrees of freedom of the scheduler and will facilitate the search for the optimal scheduling strategy. 1 We assume that the (worst-case) execution times of all atomic tasks are known and that the only uncertainty in the system is due to the fact that not all tasks need to be executed at every invocation (instance) of the program. Whether or not some task should be executed is not known in advance but is revealed as the computation goes on. Hence the program admits a finite number of execution "scenarios", each corresponding to a subset of the set of tasks.

A naive approach to solve this problem would be to enumerate all instances and solve a (deterministic) scheduling problem for each of them, but this approach ignores the dynamic nature of the uncertainty and assumes a "clairvoyant" scheduler who sees into the future. The optimal schedule achieved by such a scheduler gives only a lower-bound on the worst-case computation time of the entire program.

1 The problem of scheduling a Lustre program realizing a multi-rate control system with tasks that need to be executed periodically with different periods can be transformed into a similar acyclic scheduling problem using the following standard transformation. Suppose we have k tasks, p 1 , . . . p k with (normalized) respective periods π 1 , . . . , π k . Let π be the least common multiplier of π 1 , . . . , π k . We then construct a "main loop" of the program with π/π i copies for each task p i , with some additional constraints on the duplicate tasks so that they are forced to execute in their corresponding sub-cycles.

On the other hand, the fact that the uncertainty is bounded allows us to compute a dynamic scheduling strategy offline, without the overhead associated with online re-scheduling.

The scheduler can then be implemented as a simple add-on to the compiled code which is invoked when tasks terminate and decides, based on a pre-computed look-up table, which tasks to execute next (or to wait for the next event).

In the next section we give a more detailed yet intuitive explanation of the abstract problem that we solve.

Introduction

Consider the following program scheme:

prog1: input y x 0 := f 0 (y) x 1 := f 1 (y) if x 0 = 0 then x 2 := f 2 (y) x 3 := f 3 (y) x 4 := f 4 (x 2 , x 3 )
Each f i is a function (task) with a known computation time.

All functions except f 4 depend only on some inputs available when the program is invoked and hence can be executed immediately. The functions have no side effects and their only dependencies are via argument passing. Using data-flow analysis we can deduce that f 4 cannot be executed before both f 2 and f 3 terminate. In addition, these three statements are executed conditionally, only if x 0 = 0 holds, a fact to be revealed only after the termination of f 0 . The whole situation can be captured by the conditional precedence graph of Figure 1 where each statement x i := f i is represented as a task p i with a given duration and the condition x 0 = 0 is modeled as a special Boolean task b with a zero duration. The precedence constraints between tasks are drawn as arrows and the conditional invocation of p 2 , p 3 and p 4 is represented by their inclusion in the left side of the to b or not b box.2 Suppose we want to execute this program as quickly as possible on an architecture with two processors, assuming that communication is for free. 3 At time t = 0 we have two tasks, p 0 and p 1 , ready and we can start executing both. If after the termination of p 0 at t = 3, b evaluates to false, then all we need to do is to wait for the termination of p 1 at t = 7. If, however, b evaluates to true, p 2 and p 3 become enabled, but since p 1 still occupies one processor (we assume no preemption), we can only execute them sequentially, a fact that will delay the execution of p 4 resulting in termination at t = 15. The only reasonable alternative to this strategy is to postpone the execution of p 1 until t = 3 and then base our decision on the evaluation of b. If it turns out to be false, we start p 1 and terminate with a slight delay at t = 10. If, however, b is true, we have two free processors on which we can execute p 2 and p 3 in parallel and only then execute p 1 and p 4 and terminate at t = 13. The schedules obtained by these two strategies (we call them s 1 and s 2 , respectively) on the two cases (b and ¬b) are illustrated in Figure 2. Which strategy do we prefer? The answer depends on our evaluation criteria. If we want to be optimal with respect to the worst case, we will prefer strategy s 2 because max{10, 13} < max{7, 15}. If, however, we estimate the probability of b to be true by λ ∈ [0, 1] and want to optimize with respect to the average case, we should compare the expected termination times of the two strategies, that is, (1 -λ) • 10 + λ • 13 and (1 -λ) • 7 + λ • 15, in order to choose. It is not hard to see that s 1 is preferable when λ < 3/5 and that s 2 is preferable otherwise.

In this paper we build a framework in which problems of this kind can be formulated and solved. It consists of the following ingredients:

1. A formal model, conditional precedence graphs, for describing sets of tasks related by precedence constraints and conditional execution.

2. A translation between such models into timed game automata such that all feasible schedules correspond to runs of the automaton. Optimal scheduling is then phrased as finding shortest paths in these automata.

3. Reduction of this problem to finding shortest paths in discrete weighted game graphs.

4. Development of a heuristic forward search algorithm that can find nearly-optimal solutions for that problem.

A prototype implementation of this framework has been built and experiments with randomly-generated instances of the problem have been performed.

Conditional Precedence Graphs

The task graph (see, [START_REF] Kwong | Benchmarking and Comparison of the Task Graph Scheduling[END_REF]) is a commonly used model for describing precedence constraints between tasks. It is essentially a triple G = (P, ≺, d) where P is a set of tasks, ≺ is a strict partial-order relation on P with the intended meaning that p ≺ p if p cannot be executed before the termination of p, and d : P → N is a duration function specifying the execution time of each task. The task graph scheduling problem is concerned with finding an optimal schedule for such tasks on a given number of identical machines. In [START_REF] Abdedaïm | Task Graph Scheduling using Timed Automata[END_REF] we have shown how to translate this problem into finding shortest paths in timed automata, and were able to find optimal and nearly-optimal schedules for graphs with several thousands of tasks. Since our approach is based on search, it was also easy to incorporate additional features such as deadline and release time constraints into our tool. In this section we extend this model to express conditional execution. This is done by introducing a special type of Boolean tasks with the following features: 1) They can be preceded by other tasks; 2) They take zero time to execute;4 3) They terminate with a result which is either true or false; 4) The execution of other tasks may depend on the results of the Boolean tasks;

To express the activation conditions of tasks we will use functions over a set B of Boolean variables that encode the results of the Boolean tasks. To simplify the presentation we restrict ourselves to the class F(B) of functions that can be written as a conjunction of positive and negative occurrences (literals) of distinct Boolean variables, e.g. b 1 ∧ ¬b 2 ∧ b 3 . We denote by V (f ) the set of variables appearing in f . The partial order on Boolean functions is defined as f ≤ f if for every Boolean vector v, f (v) ≤ f (v). Syntactically this means that the set of literals in f is a superset of those of f . We say that f and f are contradictory if f ∧ f = false, which is the case when at least one variable appears positively in one and negatively in the other. Note the conjunctions can be evaluated to true only if all variable values are known, while their falsity can be sometimes deduced from partial information.

Definition 1 (Conditional Precedence Graphs)

A conditional precedence graph (CPG) is G = (P, B, ≺ , A, d) where P = {p 1 , . . . , p n } is a set of tasks, B = {b 1 . . . , b m } is a set of Boolean tasks, ≺ is a strict partial order precedence relation on P ∪ B, A : P ∪ B → F(B)
is an activation function assigning a Boolean function over B to every task, and d : P → N specifies task durations.

We use notation A p for A(p) and say that task p is less general than p if A p < A p . We denote this fact by p < p . We say that a Boolean task b influences a task p if b ∈ V (A p ) and denote it by b p.

Definition 2 (Consistent CPG)

A CPG is consistent if the following holds for every b ∈ B, and p ∈ P ∪ B:

• No speculation: if b p then b ≺ p.
No task can be executed before it is known whether it has to be executed. 5

Remark: We allow consistent CPGs to include precedence p ≺ p when p < p, that is, p may depend on a task p which might not be executed in all situations where p is. We interpret it as a conditional dependency, that is p needs to wait for p only when A p evaluates to true. Nevertheless, we disallow precedence between tasks whose activation functions are contradictory.

The definition of a feasible schedules for ordinary deterministic task-graph problems is simple. It is an assignment of start times to all tasks such that precedence constraints are satisfied and that the number of tasks active simultaneously at every moment is bounded by the number of machines. The adaptation of the definition to CPGs is more involved because different values of the B variables correspond to different sets of tasks to be executed.

An instance of the scheduling problem is an augmented Boolean vector v : B → {0, 1, } where v(b) = ("don't 5 This assumption can be relaxed if we want to move to the realm of speculative execution, used extensively in hardware. The idea is that if you have many processors you may save time by executing alternative conditional branches in parallel and then using only the outcome of the branches that really need to be executed. In that case we replace non-speculation with the weaker non circularity condition: if p b then b p. In other words, the termination of a task cannot be prerequisite for determining whether it is to be executed.

care") indicates that A b (v) is false and b need not be executed. Such situations may occur when the program admits nested if statements. A partial instance is an instance which may be undefined for some variables whose values are not known yet. We say that v extends v if it agrees with v on all variables defined in v. The set of tasks associated with an instance v is

P v = {p ∈ P ∪ B : A p (v) = true}.
A schedule for an instance v is a function st : P v → R + indicating the start times of tasks. From st we can derive for each task its termination time, en(p) = st(p) + d(p) and its execution interval The length of a schedule is defined as the termination time of the last task, that is, max p∈P v en(p). We would like to obtain schedules that are optimal for all instances, but since instances reveal themselves progressively as more Boolean tasks are evaluated, we should restrict ourselves to causal scheduling strategies that can base their decisions only on information available at decision time.

I(p) = [st(p), en(p)].
In the last couple of years we have developed a framework for expressing and solving dynamic scheduling problems using timed automata [A02], [START_REF] Abdeddaïm | Scheduling with Timed Automata[END_REF], [START_REF] Abdeddaïm | Preemptive Job-Shop Scheduling using Stopwatch Automata[END_REF] [AKM03]. The timed automaton is the natural tool for modeling the evolution of the state of the scheduling problem as a result of discrete actions (starting or ending a task, revealing the value of a Boolean task) and of the passage of time. Before describing how tasks are modeled as timed automata, let us give an informal explanation of the state-space approach to modeling scheduling problems. At any given moment the state of a scheduling problem, of the type definable by a CPG, consists of the following information:

1. Which tasks have already been executed, and for the Boolean tasks also what their result was.

2. Which tasks are currently executing and for how long.

3. For which tasks it is known whether they should be executed.

4. Which tasks, among those that should be executed, are enabled for execution (all their predecessors have terminated and not all machines are busy).

The state of the schedule determines which future evolution is possible. Passage of time increases the elapsed execution time of active tasks and allows them eventually to terminate. Termination of tasks may cause the evaluation of Boolean tasks and make some other tasks enabled. Starting a task, an action performed by the scheduler, moves a task from the waiting list to the active list and resets its timer. These actions belong to three categories:

1. Deterministic actions: these are actions that will always happen at certain states. They include termination of a task p exactly d(p) time after its initiation, and the re-evaluation of a task activation function when some new Booleans terminate.

2. Scheduler actions: these are the decisions of whether or not to start an enabled task.

3. Adversary actions: the choices of the results of Boolean tasks on which we have no control. Note that they are, nevertheless, deterministic with respect to time and happen immediately after they become enabled.

A scheduling strategy is thus a function that assigns to each state of the schedule one of the scheduler actions enabled at this state, including the special waiting "action" which means to do nothing and wait for the next event, while the active tasks keep on executing.

Modeling with Timed Automata

Timed automata [START_REF] Alur | A Theory of Timed Automata[END_REF] are automata augmented with continuous clock variables which operate in the dense time domain. A behavior (run, execution) of the automaton consists of an alternation of time passage periods where the automaton stays in the same state and the clock values grow uniformly, and of instantaneous transitions that can be taken when clock values satisfy certain conditions and which may reset some clocks to zero. In the context of scheduling, a clock reset when a certain task was started records at any moment the time spent so far in execution, and its value determines the ability of the task to take the transition that corresponds to termination.

We model scheduling problems defined by CPGs as a product of interacting timed automata. For each ordinary task p we construct a timed automaton A p with four states and one clock c as depicted in Figure 3-(a). State p? is the initial state where it is not known yet whether p is to be executed. Once A p evaluates to true, the automaton moves to a waiting state p. We can leave this state and move to the active state p as soon as the condition Π p holds, where Π p is a conjunction of conditions indicating that for every p ≺ p, automaton A p is in its terminal state. Whether or not to take this transition when Π p holds is a decision of the scheduler and when it is taken the clock is reset to zero. After spending d(p) time in the active state the automaton moves to the terminal state p. If A p evaluates to false, the automaton goes from p? directly to p.

For each Boolean task b we build an automaton (with no clock) A b as in Figure 3-(b). This automaton has three terminal states, the state b which indicates that the activation condition of b is false and hence it is not executed, and states b and ¬b to which the automaton may move when its activation condition is true and all its predecessors have terminated. As mentioned earlier, the choice between these two transition is the source of uncertainty in the scheduling problem. 6 The evaluation of activation conditions of other tasks that mention b is done on the basis of the states of the corresponding A b automata, where b? is interpreted as "unknown" and b as "don't care".

The product of all these automata (excluding states where more than k automata are in their active state) is a timed automaton in which every global state is a tuple consisting of the state of each task, including a clock for each task which is in its active state. The runs of this global automaton correspond to all the feasible schedules under all possible scheduling strategies and all adversarial choices. Readers interested in more formal details may look at [START_REF] Abdeddaïm | Scheduling with Timed Automata[END_REF].

To get the intuition let us look at Figure 4 which shows a fragment of the global automaton obtained from the CPG of Figure 1. The difference between strategies s 1 and s 2 is manifested in state (p 0 , p 1 ) where the scheduler needs to choose between starting p 1 (left sub-automaton) or waiting for the termination of p 1 (right sub-automaton). The termination of p 0 , which leads to the choice of the value of b (dashed arrows), happens at different states in each case. For s 1 , this happens when p 1 occupies one machines and consequently, when b is true p 2 and p 3 can only be executed sequentially, leading to a run of length 15. For s 2 this happens at state p 1 and both p 2 and p 3 can be executed in parallel7 leading to a schedule of length 13.

Timed automata may have an uncountable number of executions. For example, the start 1 transition from state (p 0 , p 1 ) can be taken at any time before condition c 0 = 3 becomes true, i.e. anywhere in the interval [0, 3]. A key result of [START_REF] Abdeddaïm | Scheduling with Timed Automata[END_REF] allows us to consider only a finite subset of the runs that we call non-lazy runs. A lazy run is a run in which at some state the scheduler hesitates some time before starting a task, while the global state remains the same during that waiting period. Such a laziness could be use- ful if something has changed during waiting, for example a new task became enabled or a value of a Boolean task was revealed. But if the delayed action is taken in the same global state, the waiting is useless and the schedule can be replaced by another schedule of a lesser or equal length in which the lazy action is taken as soon as it is enabled.

Restricting the search to non-lazy runs amounts to transforming the timed automaton into an ordinary finite-state automaton with numerical weights associated with its transitions, and facilitates the application of standard shortest path algorithms. Whenever a global state has several outgoing transitions, the continuations to consider are those in which a start transition is taken immediately, and those in which time (and clock values) advances by the exact amount needed to satisfy the condition for the nearest end transition. State (p 0 , p 1 ), for example, has two continuation, one is a result of starting p 1 immediately and the other is the result of waiting 3 time units until c 0 = 3 and the end 0 transition is taken.

Shortest Paths in Game Graphs

Game Graphs and Exhaustive Search

Due to the difference in the "ownership" of the start transitions (scheduler) and the transitions of Boolean tasks (environment), the object obtained after restricting the timed automaton to non-lazy runs is a kind of a game graph, also known as AND-OR graph [N71], [Z99], or alternating automaton. Such a graph has two types of nodes, OR nodes where the scheduler ("player 1") chooses an enabled transition, and AND nodes where the adversary chooses between the b and ¬b transitions. Figure 5 shows part of the game graph for our example. The outcome of applying a particular strategy is represented as a sub-graph rooted at the initial state in which every OR state has exactly one successor and every AND node has all its successors (see Figure 5). The worst case performance of such a strategy, also known as its value, is the length of the longest path in that sub-graph.

c 0 = 3 end 0 ¬b b end 1 end 3 c 3 = 2 end 1 c 1 = 7 c 4 = 8 end 0 ¬b b end 2 end 2 end 3 c 3 = 2 end 1 c 1 = 7 end 4 end 4 start 0 start 2 start 1 start 3 start 3 start 1 start 4 start 4 c 0 = 3 c 2 = 2 c 0 := 0 start 1 c 1 := 0 c 2 := 0 c 3 := 0 c 1 = 7 c 2 := 0 start 2 c 1 = 7 end 1 c 2 = 2 c 3 := 0 c 4 := 0 c 4 = 8 c 4 := 0 c 1 := 0 c 1 := 0 s 1 s 2 p 0 , p 1 0 p 0 , p 1 p 1 p 0 , p 1 p 1 , 3 p 1 , p 2 , p 3 p 1 p 1 , p 2 , p 3 p 3 p 1 , 3, p 2 , p 3 p 1 , 3 ¬b p 1 , 3, p 2 , p 3 ¬b p 1 , p 2 , p 3 p 1 , p 3 , 2 p 1 , 5, p 3 p 1 , p 4 p 1 , 7,
Since there are finitely many strategies, one could enumerate and evaluate all of them, but a more intelligent way to find the optimum is to exploit the structure of the space of strategies. Taking the left branch at q 1 is the beginning of the exploration of all scheduling strategies that decide to wait in this state. States q 5 and q 6 are two possible outcomes of this partial strategy, and any strategy that extends it has to choose what to do in each of them. Taking the right branch at q 1 starts the exploration of the rest of the strategies, each of which has to be defined for q 2 , and those that take there the right branch need to be defined for q 7 and q 8 and so on. Note that a strategy should be defined only for states reachable while applying that strategy.

Definition 4 (Game Automaton) A game automaton over a set B of Boolean variables is

M = (Q, q 0 , Σ, δ ∨ , γ, B, δ ∧ ) where Q = Q ∨ ∪ Q ∧ is a set of states partitioned into OR and AND states, q 0 ∈ Q ∨ is the initial state, Σ is a set of actions enabled at certain OR states, δ ∨ : Q ∨ × Σ → Q is a partial transition func- tion on OR states, γ : Q ∨ × Σ → R + is
a cost function defined for every q and σ such that δ ∨ (q, σ) is defined. The set B consists of positive and negative literals over the B variables and δ ∧ : Q ∧ × B → Q is the adversary (partial) transition function, defined for each q ∈ Q ∧ for exactly one pair of opposing literals.

We assume that the transition graph of the automaton is acyclic and use M q to denote the sub-automaton rooted at state q, which represents the "residual" game which remains to be played after reaching q. A state q ∈ Q ∨ is said to be terminal if δ ∨ (q, σ) is not defined for any σ. A strategy is a partial function s : Q ∨ → Σ, represented as a subgraph in which for every q ∈ Q ∨ all (q, σ) transitions are removed except for σ = s(q). A particular property of the game graphs obtained for CPGs is that all strategies induce sub-graphs which are trees with the same type of branching.

The computation of the optimal strategy is a by product of computing the value function h : Q → R + where h(q) is the value of the best strategy for the residual game M q . This function is defined recursively as:

h(q) =    0 if q is terminal min σ∈Σ γ(q, σ) + h(δ ∨ (q, σ)) if q ∈ Q ∨ min{h(δ ∧ (q, b), δ ∧ (q, ¬b)} if q ∈ Q ∧
There are various ways to compute h, one of them is the backward value iteration procedure, also known as dynamic programming, which starts with the final states and propagates values according to the definition of h until h(q 0 ) is defined. A forward depth-first algorithm is obtained by invoking h(q 0 ) and following literally the recursive definition.

If the game graph has a tree structure, this procedure has the same complexity as dynamic programming, however on non-tree graphs, the algorithm can easily become exponential since the same node can be reached via many paths. Consequently we use an algorithm that combines depth-first search with memorization: whenever h(q) is computed for the first time, the result is stored as E(q) and subsequent invocations of h(q) are answered using this value.

Algorithm 1 (Forward Value Iteration)

integer function h(q) if q is terminal return(0) elsif E(q) is defined return(E(q)) elsif q ∈ Q ∨ then begin E:=∞ for every σ such that δ ∨ (q, σ) is defined do E := γ(q, σ) + h(δ ∨ (q, σ)) E := min{E, E } E(q) := E return(E) end elsif q ∈ Q ∧ then begin E:=h(δ ∧ (q, ¬b)) E :=h(δ ∧ (q, b)) E := max{E, E } E(q) := E return(E) end
The derivation of a strategy from the value function is standard: let s(q) = σ for every q ∈ Q ∨ from which the minimum is obtained via the transition σ.

Algorithm 1 is (time and space) linear in the size of the game graph but this is not of much help because the game graph by itself is exponential in the size of the CPG. The largest problems that we could solve with this algorithm had up to 14 tasks and 4 Booleans. We have preferred this algorithm over backward dynamic programming because it is more easily amenable to techniques that find optimal or nearly-optimal solutions without exploring the whole graph.

Best First Search

Techniques for pruning the search space are based on two related ideas: 1) Do not explore paths that can easily be shown not to lead to an improvement of the value function computed so far; 2) Replace the arbitrary depth-first (or breadth-first) order of exploration by a more "intelligent" policy, which explores the more promising successors

• • • • • • • • • q 0 q 1 0 3 b ¬b b ¬b 4 0 0 4 1 0 1 • • • q 2
q 3 q 4 q 5 q 6 q 7 q 8 q 9 q 10 q 11 0 3 first. The first part of the methodology is based on an auxiliary estimation function μ(q) which approximates h(q). If this function is optimistic, that is, μ(q) ≤ h(q) for every q, we need not explore σ-successors of an OR node q satisfying E ≤ γ(q, σ) + μ(δ ∨ (q, σ)) where E is a value obtained via an already explored successor. We refer to the above condition as a safe cutting test.

• • • • • • q 12

Estimation Functions for Conditional Scheduling

For unconditional precedence graphs, an estimation function that gives a lower bound on the time remaining until termination from a state, can be constructed by first associating with each task p the length µ(p) of the longest path in the CPG from p to some terminal task. Then, the estimation μ of the value of the global state, is the maximum of µ over all tasks which are waiting or active in this state.

In the conditional setting this is more involved due to precedence constraints between tasks that have different activation conditions. Consequently the distance from a task to termination is not a single number but is instance dependent. Let µ : P × {0, 1} n → R + be a partial function defined over all v such that A p (v) is true. When A p (v) is false we use the notation µ(p, v) = ⊥. The intended meaning of µ(p, v) is the total amount of work that needs to be done for instance v before task p has started. Since computation of longest paths8 is done (explicitly or implicitly) within the (max, +)-algebra we need to extend these two operations to R + ∪ {⊥} by letting r + ⊥ = ⊥ and max{r, ⊥} = r for every r ∈ R + .

A simple way to understand this function (although not the most efficient way to compute it) is the following: for each instance v let G v be the sub-graph consisting of the tasks whose activation conditions are satisfied by v. If p does not belong to G v then µ(p, v) = ⊥, otherwise let µ(p, v) be the longest path in G v from p to termination. This function can be computed backwards on the whole graph, starting from terminal nodes: The function μ is optimistic because it takes into account precedence constraints but ignores resource constraints. In other words it assumes sufficiently many machines so that every task can be executed once all of its predecessors have terminated. A complementary way to obtain lower-bounds on schedule length is to ignore precedence constraints and take into account resource constraints, that is, dividing the total amount of work by the number of machines. The estimation

µ(p, v) = ⊥ if A p (v) = f
ν k = max v p∈P v d(p)/k
is equally optimistic as it ignores the possibility that a machine can be idle at certain times because no task is enabled. Like µ, estimation ν can be defined for global states of the game automaton by restricting summation to tasks that have not terminated.

Ordering and Sub-Optimal Solutions

As for ordering the successors of an OR node q for the purpose of best-first search, let us first note that they consist of at most k start transitions (where k is the maximal width of the CPG) and one wait transition (letting time pass until the termination of the nearest active task). A natural ordering for the start transitions is to prefer starting p i over p j whenever µ(p i , v) > µ(p j , v), giving priority to tasks that lie along the "critical path" of the problem. Although using best-first ordering turned out to reduce the number of explored states, it did not increase the size of problems that could be solved exactly and we need to resort to heuristic methods that explore small subsets of the search space which are not sufficient to guarantee optimality.

One class of heuristic methods would be the bound apriori the number of explored nodes and give the best solution found until this number is reached. To avoid getting stuck at a "local" optimum we can modify the algorithm to explore only a fixed-size subset of size w of the successors of each node, to avoid concentration on the "left" part of the search tree. Another type of heuristics is to replace the safe cutting test by a more liberal one and explore nodes only if αµ(q) < E where α is a number larger than 1 which injects some "realism" into the optimistic estimation function. The results reported in the next section are based on a heuristic that explores the w = 3 best (according to µ) successors of each OR node, uses the safe cutting test and, after exploring 80K states, switches to w = 1 to complee the exploration of some unfinished bracnches.

Experimental Results

We have implemented a tool which reads a CPG, translates it into a product of timed automata and then performs best first search, with and without guarantee for optimality, while generating states on the fly. The estimation function is computed offline and stored as a BDD. We have tested this algorithm on randomly generated CPGs on a 1.7GHz Pentium III machine with 2GB of memory. As mentioned earlier, 14 tasks and 4 Booleans is currently the upper limit for exact methods.

Table 1 gives preliminary results and indications about the applicability of our approach to large problems. For each example we find sub-optimal schedules on architectures with 3, 4 and 5 machines, using heuristic best first search. Since the exact optimum for these problem is too hard to compute, we compare these results with the lowerbound max{µ, ν k }. Note that this is not a comparison with the real optimum but with an optimistic estimation of it. We find the results rather encouraging as they demonstrate the ability to compute close to optimal scheduling policies for problems with up to 120 tasks and up to 10 Booleans. We are confident that these results can be still improved significantly by tuning the algorithm, and we look forward for testing it on real, rather than randomly-generated, examples.

Discussion

We have presented a comprehensive framework for posing and solving the important problem of optimal scheduling of conditional tasks. The overall structure of the proposed methodology is depicted in Figure 6. Our solution is based on the principle of starting with a rigorous model having a well-defined semantics, and only then moving to heuristic algorithms. Additional features such as release times and deadlines can be added very naturally [START_REF] Abdedaïm | Task Graph Scheduling using Timed Automata[END_REF], as well as communication costs. Our methodology can be applied at any desired granularity, from simple statements to procedures, and we believe that in the future it will provide a useful tool for compiling embedded software on parallel architectures and perhaps also for processor instruction scheduling. Finding the worst case optimal schedule for a program which is to be invoked periodically can determine the sampling rate (or clock rate, in hardware) with which the program can function.

The next steps in our work are the amelioration and fine tuning of the search algorithm and the development of a front end for translating programs into CPGs via data flow analysis. Further research directions include the adaptation of the algorithm to average-case analysis, the extension of our framework to speculative executions and the combination of the discrete uncertainty treated in this paper with other features we have dealt with in the past, namely preemption [START_REF] Abdeddaïm | Preemptive Job-Shop Scheduling using Stopwatch Automata[END_REF] and temporal uncertainty concerning the duration of atomic tasks [START_REF] Abdeddaïm | Scheduling with Timed Automata[END_REF].

This work is part of an ongoing effort to enrich scheduling theory with techniques based on timed automata. The reader is referred to [START_REF] Altisen | A Framework for Scheduler Synthesis[END_REF] and [START_REF] Sifakis | Building Models of Real-time Systems from Application Software[END_REF] for the general approach, to [CPP + 01], [START_REF] Kloukinas | Synthesis of Safe, QoS Extendible, Application Specific Schedulers for Heterogeneous Real-Time Systems Proc[END_REF] and [AFM + 03] for other timed automaton based tools tailored for program scheduling, to [START_REF] Asarin | Controller Synthesis for Timed Automata[END_REF] for general controller synthesis for timed automata, to [AM99], [START_REF] Niebert | Minimum-Time Reachability for Timed Automata[END_REF], and [BFH + 01] for algorithms for finding shortest paths and optimal schedules and to [M04] for a unified game theoretic framework for optimal control in the presence of adversaries.

As for other approaches to similar problems we mention the work of [START_REF] Kountouris | Efficient Scheduling of Conditional Behaviors for High-Level Synthesis[END_REF] in the context of hardware/software codesign. Although this work is also geared toward scheduling for conditional execution, it treats a much simpler problem where the only Boolean variables are clocks (in the hardware sense) whose values do not depend on the results of other tasks. Likewise, the approach taken in the timetriggered architecture [START_REF] Kopetz | The Time-Triggered Architecture[END_REF] does not consider dependencies among tasks. It determines manually the distribution of tasks on machines and then focuses on finding schedules for the common bus through which they communicate.

Figure 2 .

 2 Figure 1. A conditional task graph representation of the program.

Figure 3 .

 3 Figure 3. Modeling tasks with timed automata: a) ordinary tasks; b) Boolean tasks.

Figure 4 .

 4 Figure 4. Part of the global automaton for the example of Figure 1. In the states we write only the waiting tasks, the executing tasks and the values of their non zero clocks. The numbers on the lower right corners stand for the total elapsed time to reach the state via a non-lazy run. The branches correspond to the schedules of Figure 2.

Figure 5 .

 5 Figure 5. Part of the game graph for our example, with AND nodes denoted by squares. The sub-graph of strategy s 2 is marked.

  alse d(p) otherwise and computing for other nodes as µ(p, v) = d(p) + max p :p≺p µ(p , v). This computation can be done symbolically (and offline) using the syntax of A without necessarily enumerating all instances. From µ we can define an estimation function μ over the states and clock values of the A p automaton by letting μ(p?, c, v) = μ(p, c, v) = µ(p, v), μ(p, c, v) = µ(p, v) -c and μ(p, c, v) = µ(p, v) -d(p).

Figure 6 .

 6 Figure 6. The overall methodology.

  The number of active tasks at time t is β(t) = |{p : t ∈ I(p)}|.

	Definition 3 (Feasible Schedules) A schedule st for an in-
	stance v is feasible on an architecture with k machines if
	1. Precedence: for every p ∈ P

v , st(p) ≥ max{en(p ) : p ∈ P v ∧ p ≺ p}. A task may start only after all its predecessors have terminated.

2. Resource constraints: for every

t ∈ R + , β(t) ≤ k.

No more than k tasks may be active simultaneously.

Table 1 . Results for applying bounded best first search to some large examples Column len indi- cates the worst-case length of the best solution found, time indicates computation time (in min- utes), nb st is the number of explored states and dev is the deviation from the (optimistic) lower- bound.

 1

	k	3				4			5
	(n, m)	len time	nb st	dev	len	time	nb st	dev	len time	nb st	dev
	100, 6	268 2:37 119648 3.07%	198	3:26 126703 1.53%	162 4:10 141319 3.84%
	100, 7	316 3:36 142602 0.00%	238	4:12 159369 0.42%	192 4:20 158961 1.05%
	120, 7	357 4:15 143480 0.84%	270	6:20 182788 1.50%	218 3:40 101104 2.34%
	100, 10	480 6:51 190163 2.78%	371 10:03 244199 6.00%	345 5:58 116089 3.60%

Unfortunately not all conditional precedence graphs can be drawn so neatly.

This assumption can be relaxed at the price of complicating the presentation as well as the computation (because some of the symmetry in the system is lost).

This can be relaxed if testing the condition takes non-negligible amount of time, but such tests can be decomposed into an ordinary task and a zero duration test.

Note also that these two branches never meet again, a fact the induces a special structure of the product automaton which distinguishes it from other types of game graphs.

The fact that the start 2 and start 3 are executed one "after" the other is just an artifact of the interleaving semantics; No time passes between these two transitions and they happen at the same metric time.

The reader should not confuse the precedence graph (CPG) on which we compute longest paths, as in PERT, with the transition graph of the game automaton on which we seek shortest paths.

Acknowledgments Part of the motivation of this work is due to discussions with P. Caspi and S. Tripakis concerning the scheduling of Lustre programs. Helpful comments were given by P. Niebert, A. Asarin, Ph. Gerner, S. Cotton, S. Yovine, A. Curic, R. Rajkumar, I. Broster, A. Pnueli and anonymous referess.

* This work was partially supported by the European Community projects IST-2001-35304 AMETIST (Advanced Methods for Timed Systems), IST-2001-38117 RISE (Reliable Innovative Software for Embedded Systems) and IST-2001-33520 CC (Control and Computation) and by a grant from Intel.