Louis-Claude Canon

Adel Essafi

Denis Trystram

A Proactive Approach for Coping with Uncertain Resource Availabilities on Desktop Grids

Keywords: Scheduling, Desktop grids, Uncertainties, Availabilities

Uncertainties stemming from multiple sources affect distributed systems and jeopardize their efficient utilization. Desktop grids are especially concerned by this issue as volunteers lending their resources may have irregular and unpredictable behaviors. Efficiently exploiting the power of such systems raises theoretical issues that received little attention in the literature. In this paper, we assume that there exist predictions on the intervals during which machines are available. When these predictions have a limited error, it is possible to schedule a set of jobs such that the effective total execution time will not be higher than the predicted one. We formally prove it is the case when scheduling jobs only in large intervals and when provisioning sufficient slacks to absorb uncertainties. We present multiple heuristics with various efficiencies and costs that are empirically assessed through simulations.

Introduction

Harnessing the power of modern parallel platforms is compromised by many uncertainties coming from their high scales and resources volatility. In this work, we focus on desktop grids, which gather idle computing resources of common desktops distributed over the Internet for running massively parallel computations. Such systems provide a very large computing power for many applications issued from a wide range of scientific domains [START_REF] Larson | Folding@Home and Genome@Home: Using distributed computing to tackle previously intractable problems in computational biology[END_REF][START_REF]The Einstein@Home search for periodic gravitational waves in LIGO S4 data[END_REF]. Most of these parallel applications are composed of workflows of sequential jobs that are submitted by successive batches to a particular user interface machine. Then, the corresponding jobs are transferred and executed on the distributed available resources according to some scheduling policy.

Usually the resources are not continuously available over time since users give their idle CPU time only for some periods when they are not using their desktops. Moreover, even if the dates of unavailability periods can easily be estimated in advance, they are subject to uncertainties. This may drastically impact the global performances by delaying the completion of the whole application.

In this paper, we study how to schedule efficiently a set of jobs under the constraints of unavailability periods. At the same time, we are interested in reducing the effect of disturbances on the unavailabilities by maximizing the stability that measures the ratio between the maximum completion time (makespan) of the disturbed instance over a predicted completion time [START_REF] Billaut | Flexibility and Robustness in Scheduling[END_REF].

To the best of our knowledge, there is no related work studying scheduling with unavailability under uncertainties except our previous contribution [START_REF] Canon | A Bi-Objective Scheduling Algorithm for Desktop Grids with Uncertain Resource Availabilities[END_REF] which provided a preliminary analysis for restricted disturbance patterns. Our proposed approach relies on a slack-based proactive approach (with temporal protection). The uncertainties are taken into account before job executions such that the execution of the generated schedule is robust to variations in the environment characteristics. As the execution of some jobs may be interrupted, we introduce slacks just before each unavailability period. The problem consists then in assigning each job to an availability (like in a classical bin packing) while preserving enough idle time in the slack whose lengths depends on the allocated jobs.

The first contribution is to investigate the problem of scheduling with unavailabilities from the view point of studying the effect of uncertainties on the availability periods. We characterize general conditions that any schedule must verify to obtain an optimal stability (i.e., with a disturbed completion time not worse than the predicted one). The processors are assumed to be uniform whereas they were identical in our previous work [START_REF] Canon | A Bi-Objective Scheduling Algorithm for Desktop Grids with Uncertain Resource Availabilities[END_REF]. Moreover, we consider that unavailabilities can start not only earlier than expected but also later. Our main contribution is the design of a complete set of algorithms and their analysis. The proposed bounds on the stability outperform our previous one. Additionally, the algorithmic scheme relies on global procedures that use either greedy or dual approximation paradigms. Each of these procedure uses a local procedure, including a novel dynamic programming, for assigning jobs to a given availability. Then, the good behaviour of the algorithms is assessed by running simulations derived from actual workflows of BOINC [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF].

The paper is organized as follows. We start by briefly recalling the most significant studies on scheduling under availability constraints in Section 2. Section 3 is devoted to the description of the computation model and the formal presentation of the problem. Section 4 provides a structural analysis of the proposed slack-based mechanism in terms of stability. Then, Section 5 describes the various algorithms and their combinations. Before concluding, Section 6 presents some experiments based on simulations on actual workflows and availability constraints.

Related Work

In this section, we recall briefly the most significant works related to the problem of scheduling under unavailability constraints.

Most of the existing approaches that addressed the problem of scheduling with unavailabilities are based on the well-known LPT rule (Largest Processing Times) for which many assumptions have been explored. For instance, Lee [START_REF] Lee | Parallel machines scheduling with nonsimultaneous machine available time[END_REF][START_REF] Lee | Machine scheduling with an availability constraint[END_REF] introduced the problem of scheduling independent jobs with several availability patterns. He showed that the problem is not polynomially approximable if no restrictions are done on the availabilities. This is a commonly accepted result which shows that without specific assumptions the problem may lead to an non-feasible solution. Hwang and Chang [START_REF] Hwang | Parallel Machines Scheduling with Machine Shutdowns[END_REF] have analyzed the problem when no more than half of the machines are unavailable simultaneously. Liao et al. [START_REF] Liao | Makespan minimization for two parallel machines with an availability constraint[END_REF] studied the restriction of the problem on two machines where each machine has one fixed unavailability period. A variant of this particular problem was studied in [START_REF] Xu | Makespan minimization for two parallel machines scheduling with a periodic availability constraint[END_REF] where the first machine is always available whereas periodic unavailabilities are scheduled on the second. The problem where one machine is always available and with an arbitrary number of unavailabilities on the other processors was analyzed in [START_REF] Diedrich | Approximation Algorithms for Scheduling with Reservations[END_REF]. Although this problem does not admit Fully Polynomial Time Approximation Scheme (FP-TAS), a costly PTAS based on the multiple knapsack was designed [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems: theoretical and practical results[END_REF]. While all the previous approaches are related to sequential jobs, Eyraud et al. [START_REF] Eyraud | Analysis of Scheduling Algorithms with Reservations[END_REF] studied the problem of scheduling with unavailabilities for parallel rigid jobs.

a k i u k i e k-1 i e k i s k i machine i
Figure 1: Representation of interval k on machine i, which contains an availability period followed by an unavailability period.

They proved that there is no approximation algorithm in the general case, and they proposed an approximation algorithm for non-increasing unavailability patterns.

We developed a preliminary study of scheduling under unavailability constraints with uncertainties in [START_REF] Canon | A Bi-Objective Scheduling Algorithm for Desktop Grids with Uncertain Resource Availabilities[END_REF]. Each interrupted job was restarted from the beginning, without migration, but the unavailability constraints were only allowed to advance forward.

The solution proposed here is much more general. It is based on the introduction of a slack mechanism before the unavailability intervals. Several studies used the same idea and proposed proactive heuristics based on slacks in different contexts. In [START_REF] Fallah | Preemptive resource constrained project scheduling problem with uncertain resource availabilities: Investigate worth of proactive strategies[END_REF], the authors investigate the use of preemption. In [START_REF] Lambrechts | Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities[END_REF][START_REF] Lambrechts | Time slack-based techniques for robust project scheduling subject to resource uncertainty[END_REF], the authors explored stochastic resource breakdown.

3 Description of the Problem

Execution Model

The target parallel platform is composed of m uniform machines (also called processors) that are indexed by i in the rest of the paper. The cycle time of processor i is denoted by b i , which is the inverse of its speed. The workload consists of n independent jobs that are indexed by j. The processing amount of job j is denoted by p j . Hence, the duration of job j executed on processor i is b i p j . Moreover, each machine is subject to a set of unavailability constraints. An interval is defined as an availability followed by an unavailability. The intervals are indexed by k and the start date of unavailability period k on processor i is denoted by s i (k). As depicted in Figure 1, the availability (resp. unavailability) has a duration of a i (k) (resp. u i (k)). Hence, this period ends at e i (k) s i (k) + u i (k) and we also have s i (k) a i (k) + e i (k -1). To be consistent, the first availability on processor i starts at e i (0) (by default, s i (0) = -∞ and no job is scheduled on the 0th interval) and there are K i intervals on machine i. The job durations are assumed to be bounded such that 2p max ≤ a min where p max is the maximum job duration (i.e., max 1≤i≤m,1≤j≤n b i p j ) and a min is the shortest availability (i.e., min 1≤i≤m,1≤k≤K i a i (k)).

s k i e k i δ k i δ k i machine i

Disturbance Model

Solving scheduling problems with uncertain data has received recently a great attention. There exist several possible approaches depending on the target problem and the desired objectives. The survey of Billaut et al. [START_REF] Billaut | Flexibility and Robustness in Scheduling[END_REF] discusses several complementary approaches from pure proactive methods (sensitivity analysis), pure online strategies and semi online methods (flexibility). We focus here on this last approach which consists in building an efficient solution on estimated data followed by correction mechanisms at runtime. Let δ i (k) be the disturbance that impacts the kth unavailability period on processor i. The disturbed start date of this unavailability is s i (k) + δ i (k) and its disturbed end date is e i (k) + δ i (k).

As shown in Figure 2, the start and end dates are disturbed, but not the unavailability durations (i.e., u i (k) remains constant). Moreover, the disturbances are limited to a restricted interval to limit prediction errors, i.e., -a i (k) ≤ δ i (k) ≤ a i (k + 1). This assumption ensures that there are at most two interruptions per interval.

Problem Definition

The objective is to generate a schedule given a set of jobs and a set of machines with their unavailability constraints. A schedule is specified by an allocation function π i (k) that provides the set of jobs to be executed during each kth interval on each ith processor. We restrict this study to feasible schedules, i.e., schedules for which the availability periods are long enough for any job execution. Assessing the quality of a schedule is done through two objectives: the efficiency and the ability to cope with uncertainties.

The first objective is the horizon λ, which measures the performance and is specified while building the schedule. Since jobs allocated to any interval must fit in the availability, the horizon is then greater than or equal to the makespan without uncertainties (C max max 1≤j≤n C j where C j is the completion time of job j in a given schedule [START_REF]Handbook of Scheduling: Algorithms, Models, and Performance Analysis[END_REF]). In [START_REF] Canon | A Bi-Objective Scheduling Algorithm for Desktop Grids with Uncertain Resource Availabilities[END_REF], we have considered the makespan instead of an horizon. As a consequence, we assumed that at least one processor did not have any unavailability which is unrealistic and not required anymore. Using an horizon provides thus more flexibility and is more general as it may be equal to the makespan as a special case.

The second objective is the stability. It is defined as the ratio between the highest disturbed makespan C max among all possible disturbed scenarios and the specified horizon λ, i.e., σ Cmax λ . It represents the insensitivity of a schedule to disturbances. A schedule is stable if σ ≤ 1 (values strictly lower than one are not necessary and may impair the efficiency). The problem consists in determining a schedule with minimum values of horizon and stability.

Discussion

The proposed models rely on some assumptions that are briefly discussed below.

The 2p max ≤ a min assumption has been confronted to actual data from the Failure Trace Archive [START_REF] Kondo | The failure trace archive: Enabling comparative analysis of failures in diverse distributed systems[END_REF]. Among a sample of five millions availabilities, 95% of the computing time is distributed in availabilities longer than two hours, which is much greater than the duration of common desktop grid jobs. Moreover, the assumption could be relaxed by considering each processor separately (i.e., by assuming that for each processor, twice its longest allocated job must be lower than its shortest availability). Theoretically, this assumption avoids interruptions to occur in cascade indefinitely (the same job being interrupted by every unavailability).

The -a i (k) ≤ δ i (k) ≤ a i (k + 1) assumption reflects the precision of the prediction. Performing a static allocation strategy would be irrelevant if the prediction error was too high. The disturbance model also supposes that each unavailability can interrupt only one job and that the unavailability durations remain constant, which implies that the ratio between availabilities and unavailabilities remains constant.

Dealing with Uncertainties

In this section, we present a mechanism based on the insertion of a slack inside each availability. The size of each slack that is required to obtain stable schedules should be carefully determined. Moreover, we assume that at runtime jobs scheduled in interval k are not started before jobs scheduled in interval k -1 has not been completed for any 1 < k ≤ K i (i.e., the order between the allocations of each interval is preserved).

Definition 1 (Slack). The slack d i (k) is the amount of idle time reserved in availability k on processor i in a given schedule.

Let M i (k) max j∈π i (k) b i p j be the duration of the longest job assigned to the kth interval on processor i

(M i (k) 0 if π i (k) = ∅ or if k ≥ K i ).

Definition 2 (Slack rule). A schedule respects the slack rule if and only if

d i (k) ≥ max(M i (k), M i (k + 1), M i (k + 2))
for each interval k and for each machine i. Proposition 1. When 2p max ≤ a min and when the jobs are executed without delay, any schedule respecting the slack rule is stable.

Proof. The proof is by induction on the interval indexes using a single machine as it is illustrated in Figure 3. The induction hypothesis H(k) is that all jobs scheduled in the first k intervals have been executed before the following date (three cases):

1. e i (k) if unavailability k is early (i.e., δ i (k) ≤ 0); 2. s i (k) -d i (k) if unavailability k is late and unavailability k -1 finishes before s i (k) -d i (k); 3. s i (k) -d i (k) -u i (k -1) -d i (k -1) otherwise (i.e., if unavailability k is late and unavailability k -1 finishes after s i (k) -d i (k)).
Induction basis for k = 2. Previous cases are enumerated (see Figure 4). In case 1), unavailability 2 is early. When unavailability 1 starts before s i (1)d i (1) (case a), the worst case occurs when this unavailability interrupts the longest job of this interval, which size is M i (1). As the slack rule is respected,

d i (1) ≥ M i (1)
and the interrupted job can be executed again before e i (1) with all uninterrupted jobs scheduled in the first interval. Similarly, unavailability 2 interrupts the job of size M i (2) and the slack is large enough for re-executing it. When unavailability 1 starts after s i (1)

-d i (1) (case b), all jobs scheduled FEMTO-ST Institute k -1 k k + 1 d i (k -1) d i (k) d i (k + 1) s i (k) e i (k) s i (k + 1) e i (k + 1)
stable by H(k) induction step

Figure 3: Induction on the intervals for the proof of Proposition 1. in interval 1 are executed before s i (1) -d i (1). Then, unavailabilities 1 and 2 interrupt the longest job scheduled in interval 2. As both slacks are greater than or equal to M i (2), then this job may be restarted and completed before e i (2). In case 2), unavailability 2 is late and unavailability 1 finishes before s i (2)d i (2). In the worst case, unavailability 1 will interrupt the longest job scheduled in the first two intervals. As the slack rule is respected,

1 2 p 1 p 2 p 3 d i (1) s i (1) e i ( 1
)
d i (2) s i (2) e i (2) 1 2 1) p 1 p 1 p 2 p 3 p 3 1 2 2) p 1 p 2 p 3 p 3 1 2 3) p 1 p 2 p 3
d i (1) ≥ max(M i (1), M i (2)).
Then, all jobs scheduled in these intervals terminate before

s i (2) -d i (2).
Finally, case 3) is when unavailability 2 is late and unavailability 1 finishes after s i (2) -d i (2). In this case, all jobs scheduled in the first two intervals are executed without interruption. Thus, they finish their executions at

s i (2) - d i (2) -u i (1) -d i (1)
. Therefore, H(2) is true. Induction step. H(k) is assumed to be true for a given k ≥ 2. We consider again three cases depending on the date of unavailability k. In case 1), unavailability k is early and all jobs scheduled in the first k intervals are executed before e i (k) by induction hypothesis. Given the assumptions on the online strategy, the jobs scheduled in interval k + 1 may start in interval k (i.e., before e i (k)). Although these jobs may be interrupted by previous unavailabilities, they are assumed to be restarted in interval k + 1 (i.e., after time e i (k)) during which they can only be interrupted by unavailability k + 1. We show that H(k + 1) is true when unavailability k is early by considering that unavailability k+1 is either early or late analogously to the induction base case. In the earliness case (case a), unavailability k + 1 interrupts the longest job scheduled in interval k + 1 and the slack can absorb it before e i (k + 1). Otherwise (case b), jobs scheduled in interval k + 1 are not interrupted and finish thus before

s i (k + 1) -d i (k + 1).
In case 2), unavailability k is late, unavailability k -1 finishes before s i (k -1) -d i (k -1) and all jobs scheduled in the first k intervals are executed before s i (k) -d i (k) by induction hypothesis. We prove below that if unavailability k+1 is early (case a), then jobs scheduled in interval k+1 can be executed between s i (k) -d i (k) and e i (k + 1). This duration comprises enough slack to tolerate the longest job to be interrupted twice, by unavailability k, which is late, and by unavailability k + 1, which is early:

d i (k) ≥ M i (k + 1) and d i (k + 1) ≥ M i (k + 1
). In the case when unavailability k + 1 is late (case b), unavailability k finishes either before or after s i (k + 1) -d i (k + 1). In the first case (case b.1), unavailability k can interrupt the longest job scheduled in interval k + 1, which can be absorbed by slack d i (k) ≥ M i (k + 1). Thus, jobs scheduled in the first k + 1 intervals are completed before s i (k + 1) -d i (k + 1). In the second case (case b.2), no job is interrupted in interval k + 1 and these jobs are completed before s i (k + 1)

-d i (k + 1) -u i (k) -d i (k).
In case 3), unavailability k is late, unavailability k -1 finishes after s i (k -1) -d i (k -1) and all jobs scheduled in the first k intervals are executed before

s i (k) -d i (k) -u i (k -1) -d i (k -1
) by induction hypothesis. Thus, jobs scheduled in interval k +1 are executed after this date. Since 2p max ≤ a min and δ i (k -2) ≤ a i (k -1), unavailability k -2 (for k ≥ 3) cannot interrupt any of these jobs. Remark that this is true even when shifting the first unavailability that finishes after the horizon makes the last availability shorter than a min because 2p max needs to be lower than or equal to the availability duration of an interval k that is never the last one. If unavailability k + 1 is early (case a), then the longest job among the jobs scheduled in interval k + 1 can be interrupted by unavailabilities k -1 to k + 1. As d i (k -1), d i (k) and d i (k + 1) are all greater than or equal to M i (k + 1), there is enough duration between

s i (k) -d i (k) -u i (k -1) -d i (k -1
) and e i (k + 1) to absorb these three interruptions. The last two cases (b.1 and b.2) can be derived analogously.

In every cases, the induction hypothesis H(k + 1) is true when H(k) is supposed to be true, which concludes the proof in the general case.

The previous proof does not require any information on the platform characteristics because each machine is considered independently. Thus, Proposition 1 holds for any kind of parallel platforms (identical, uniform and unrelated). Additionally, the problem of generating a schedule that respects the slack rule with an optimal makespan can be proven to be NP-Hard using the same proof as in [START_REF] Canon | A Bi-Objective Scheduling Algorithm for Desktop Grids with Uncertain Resource Availabilities[END_REF].

Algorithms

Preliminary

We propose several heuristics and present them using the following notation: S i (k) = j∈π i (k) b i p j (i.e., the sum of the duration of the jobs scheduled on the kth interval of machine j). Moreover, we assume that d i (k) = ∞ for each k ≤ 0 (i.e., there is an infinite amount of idle time on non-existing intervals).

The proposed heuristics are based on a global method that prepares the intervals by shifting and sorting them. A local scheduling policy then assigns the jobs to the intervals. Each local method relies on a common mechanism for identifying the longest job that can be scheduled on a given interval. Before covering the different local methods, this mechanism is described below. This section ends with the description of the two global methods that can both use any local methods.

Algorithm 1 computes the duration of the longest job that can be scheduled on one interval. The current slack must account for the longest jobs scheduled on the three next intervals (this corresponds to the base case of Proposition 1). Moreover, any candidate job must also fit in the previous slacks due to the slack rule when applied to the previous intervals.

Algorithm 1 Procedure longestJob(i, k) Input: the slack of intervals k -2 to k (d i (k -2), d i (k -1) and d i (k)) and
the length of the longest jobs scheduled on intervals k to k + 2 (M i (k), M i (k + 1) and M i (k + 2)) Output: the length of the longest job that can be allocated on interval k of machine i

1: prev ← min(d i (k -2), d i (k -1)) {The candidate job must fit in previous slacks} 2: curr ← d i (k) 2 {The candidate job must fit in the current slack} 3: next ← d i (k) -max(M i (k), M i (k + 1), M i (k + 2)
) {Slack rule base case} 4: return min(prev, curr, next)

Local Scheduling Policies

Local scheduling policies consider intervals as bins that are successively considered for allocating jobs. These policies are then used with higher-level heuristics that select the intervals and the order in which they are visited. Local policies assume therefore that they are given an ordered set of intervals to which a set of jobs have to be allocated. The output is an allocation function π that provides the set of jobs to be executed during each kth interval on each processor.

The first scheduling policies are the classical LPT (Longest Processing Time) and SPT (Shortest Processing Time). These strategies ignore the order between the intervals and schedules jobs according to their finishing times. This finishing times include the slack to ensure that any disturbed makespan is never larger than the horizon. The only difference between LPT [4, Algorithm 2] and SPT is that the first algorithm considers jobs in non-increasing order of their processing costs, while it is non-decreasing for the second.

Algorithm 2 Longest Processing Time (LPT)

Input: a set of n jobs, a set of m machines with unavailabilities Output: an allocation function π 1: J ← {j 1 , j 2 , . . .} such that p j l ≥ p j l+1 {Sort jobs by non-increasing processing cost} 2: for all j ∈ J do {Consider each job in given order}

3:

E min ← ∞ 4:
for all 1 ≤ i ≤ m do {Consider each machine i candidate for allocation}

5: k ← 1 6:
while b i p j > longestJob(i, k) do {Search for the first unavailability}

7: k ← k + 1 8:
end while

9: E ← e i (k -1) + S i (k) + b i p j + max(b i p j , M i (k), M i (k + 1), M i (k + 2)) 10:
if E < E min then {Earliest end date of job j on machine i, slack included} (i , k ) ← (i, k)

π i (k ) ← π i (k ) ∪ {j}
{Schedule job j in interval k on machine i } 16: end for 17: return π For clarity, we ignore the time taken to sort the jobs, O(n log(n)), when characterizing the complexity of local scheduling policies. The complexity of LPT is O(nK), which is the number of jobs times the total number of reservations (K = m i=1 K i ). For SPT, it is O(nm + K) because when a job does not fit into an interval, any subsequent jobs will not fit either.

We also use two well-known bin-packing heuristics, namely First Fit Decreasing (FFD) and First Fit Increasing (FFI). With FFD [4, Algorithm 3], jobs are considered in non-increasing order and each one is allocated to the first interval for which the slack rule is respected. While FFD shares the same complexity with LPT, FFI has time complexity of O(n + K) (plus the time for sorting the jobs).

Algorithm 3 First Fit Decreasing (FFD)

Input: a set of n jobs, a sequence of intervals I = {(i 1 , k 1 ), (i 2 , k 2 ), . . .} Output: an allocation function π 1: J ← {j 1 , j 2 , . . .} such that p j l ≥ p j l+1 {Sort jobs by non-increasing processing cost} 2: for all (i, k) ∈ I do {Consider each interval k on machine i in given order}

3:

for all j ∈ J do {Consider each job in given order}

4:

if b i p j ≤ longestJob(i, j) then end for 9: end for 10: return π We also propose a new algorithm based on the dynamic programming paradigm, DPslack [4, Algorithm 4], that is derived from the classical knapsack dynamic programming solution. First, jobs are sorted by non-decreasing processing cost. Then, for each interval (in the given order), we compute recursively the value P s (m, a i (k)), which is the maximum duration during which a subset of the first m jobs can be executed in the first a i (k) time units of this interval (which is distinct from a i (k) due to the slack rule and the fact that jobs may not fit perfectly in the interval). The recurrence relation is

P s (j, l) = max(P s (j -1, l), P (j -1, l -b i p j -max(b i p j , M i (k + 1), M i (k + 2))) + b i p j ) P (j, l) = max(P (j -1, l), P (j -1, l -b i p j ) + b i p j )
with the initialization P s (j, l) = P (j, l) = 0 for 0 ≤ j ≤ m, 1 ≤ l ≤ a i (k) and with P (j, l) corresponding to the related knapsack problem without the slack constraint. As the jobs are ordered, the removed quantity due to the slack if job j is selected is done only for the last added job (i.e., b i p j instead of M i (k)), which is indeed the longest. The complexity of DPslack is O(na max K) where a max = max 1≤i≤m,1≤k≤K i a i (k) is the maximum availability duration.

Algorithm 4 DPslack (Dynamic Programming) Input: a set of n jobs, a sequence of intervals I = {(i 1 , k 1 ), (i 2 , k 2 ), . . .} Output: the allocated set of jobs π i (k)

1: J ← {j 1 , j 2 , . . .} such that p j l ≤ p j l+1 {Sort jobs by non-decreasing processing cost} 2: for all (i, k) ∈ I do {Consider each interval k on machine i in given order}

3:

Initialize each element of matrices P and P s to 0 4: for all j ∈ J do {Consider each job in given order} 5:

if b i p j ≤ longestJob(i, k) then 6:
for all 1 ≤ l ≤ a i (k) do {Consider a sub-interval} 7:

P [j][l] ← P [j -1][l] 8: P s [j][l] ← P s [j -1][l] 9:
if b i p j ≤ l then {Check if the job fits} 10:

P [j][l] ← max(P [j][l], P [j -1][l -b i p j ] + b i p j ) 11: d ← max(b i p j , M i (k + 1), M i (k + 2)) 12:
if b i p j + d ≤ l then {Check if the job and its slack fits} 13:

P s [j][l] ← max(P s [j][l], P [j -1][l -b i p j -d] + b i p j ) 14:
end if for all j ∈ J do {Consider each job in reverse order} 22: end for 31: end for 32: return π

if (P s [j][l] = P s [j -1][l] or not s) and (P [j][l] = P [j -1][l] or s) then 23: π i (k) ← π i (k) ∪ {j} 24: l ← l -b i p j 25: if s then 26: l ← l -max(b i p j , M i (k + 1), M i (k + 2))

Global Scheduling Policies

The global scheduling policies prepare the instance by shifting and sorting the intervals before calling local ones for scheduling each job. Any scheduling policy can then be used (FFI, FFD, SPT, LPT, DPslack) with both following strategies.

First, we present a greedy strategy, GreedySlack [4, Algorithm 5], in which availabilities are sorted by non-decreasing end date of unavailability. Intervals are shifted by advancing their unavailabilities as much as possible, which corresponds to the worst case. The horizon is the end date of the last allocated job plus the associated slack. The complexity of this strategy is O(K log(K)) and it calls a local policy only once. While LPT and SPT are only affected by the shifting of the intervals and not their order, it is the contrary for bin-based heuristics (FFI, FFD and DPslack). for all 0 ≤ k < K i do {For all unavailabilities} e i (k) ← e i (k) + u i (k + 1)

5:

end for 6:

K i ← K i -1 7: end for 8: I ← {(i 1 , k 1 ), (i 2 , k 2 ), . . .} such that s i l (k l ) ≤ s i l+1 (k l+1 ) {Sort intervals by
non-decreasing availability end date} 9: Call a scheduling policy with I and the jobs to obtain π 10: return π

The second solution, DAslack ([4, Algorithm 6]), uses the dual approximation paradigm that consists in scheduling all jobs within various horizons until the minimum one is reached (by binary search) [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems: theoretical and practical results[END_REF]. For each horizon, the availabilities are sorted by non-decreasing duration because we assume it is easier to fill small availabilities first. The complexity of this strategy is O(K log(K)) for sorting the intervals. It calls a local strategy O(log(M )) times where M is an upper bound on the horizon and it takes O(log(K)) steps to adapt the intervals each time. For instance, the complete complexity of the combination DPslack and DAslack is O(K log(K) + n log(n) + log(M )(log(K) + na max K)) (sorting the jobs has to be done only once).

Algorithm 6 DAslack (Dual Approximation)

Input: a set of n jobs, a set of m machines with unavailabilities Output: an allocation function π 1: u ← upper bound on λ (e.g., max 1≤i≤m,1≤k≤K i e i (k)) 2: l ← lower bound on λ (e.g., 0)

3: while u -l > 1 do 4: λ ← u+l 2 5:
for all 1 ≤ i ≤ m do {All machines} 6:

for all 0 < k ≤ K i do {All unavailabilities} 7:
if e i (k) > λ then {Move last interval} 8:

s i (k) ← max(λ -u i (k), e i (k -1)) 9:
e i (k) ← λ if e i (k) = λ then {Discard the next intervals} 12:

K i ← k 13:
end if Call a scheduling policy with I and the jobs to obtain π 18:

I ← {(i 1 , k 1 ), (i 2 , k 2 ), . . .} such that a i l (k l ) ≤ a i l+1 (k l+1 )
if π is invalid then end if 23: end while 24: return last valid schedule FEMTO-ST Institute

Experiments

We evaluated the proposed algorithms by simulating the execution of a set of jobs on a set of availabilities issued from an actual trace gathered from BOINC using the scheduling algorithms proposed in Section 5 in order to observe the impact of the slack on their stability.

Settings

Availabilities

The traces of the hosts were gathered by BOINC clients that were installed on volunteer hosts between April 1, 2007 and January 1, 2009 for the SETI@home project [START_REF] Javadi | Discovering statistical models of availability in large distributed systems: An empirical study of seti@home. Parallel and Distributed Systems[END_REF]. In total, about 230,000 hosts were involved and provided over 57,800 years of CPU availability spread on 102,416,434 intervals continuous intervals. We selected 10 arbitrarily subsets of 500 processors in the middle of the trace and only processors for which the speed is known were selected.

Workload

The traces of the jobs were collected from Docking@Home project1 and provided over 150,000 jobs. We selected 10 subsets of 10,000 jobs. Each execution duration is rounded to the closest integer in second.

Disturbed Instance Generation

In order to generate disturbed instances, we modified the start and end times of the availabilities following a uniform law. Unavailabilities that overlap following this process were merged.

Methodology

We performed three sets of simulations to study the main characteristics of the proposed algorithms:

Performance In order to compare the performance of the proposed algorithms in terms of schedule length, we run all the algorithms and measured the horizon. For each instance, we computed the ratios between the horizons obtained with all heuristics and the minimum horizon among this set.

Stability Following the adopted proactive scheme, the execution scenarios are run in two phases: each schedule algorithm is first run using the predicted non-disturbed dates before being run on 30 disturbed instances.

Execution time

We measured the execution time to build any schedule.

Analysis

As a baseline, we included a version of each algorithm that ignores the slack rule (denoted without slack rule in Figures 5 to 7). These figures depict values using boxplots in which the bold line is the median, the box shows the quartiles, the bars show the whiskers (1.5 times the interquartile range from the box) and additional points are outliers.

Performance Comparison

Figure 5 show the horizon ratios for each heuristic. For instance, the horizon obtained with LPT are about 1.5 times the minimum horizon that can be obtained with any other heuristic. We first observe that any heuristic that ignores the slack rule is significantly better than its counterpart (respecting the slack rule incurs at least a 50% degradation). Additionally, those that use DAslack are among the best ones.

We can also see that DAslack leads to better results than GreedySlack except for SPT and LPT, which do not benefit from the binary search. Moreover, with GreedySlack, LPT outperforms bin-based heuristics (FFI, FFD and DPslack) due to the last bins that are filled even though the jobs could finish earlier on other machines. Using DAslack limits this problem as the last bins are cut.

Overall, the best heuristic is LPT (with both general policies), followed by FFD combined with DAslack.

Impact of the Slack on the Stability

The boxplots in Figure 6 represent the ratios between the disturbed values of the makespan and the predicted horizons. Schedules are always stable (stability below one) with heuristics that respect the slack rule, which is consistent with Proposition 1. The least stable strategies (those that do not respect the slack rule) lead also to the most compact schedule as suggested by Figure 5. Inversely, the most stable ones (FFI, SPT and DPslack combined with GreedySlack) are also the least efficient ones. This emphasizes, as expected, the antagonism between the efficiency and the stability. GreedySlack DAslack q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.8 GreedySlack DAslack q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 1 100 10000

Execution Time

Figure 7 depicts the execution times of the heuristics, which are sorted by their execution times. The ratio between the execution times of GreedySlack strategies and DAslack is constant as this last strategy repeats each local policies the same number of times. Overall, the fastest local policy is FFI while the slowest is DPslack and all other policies have similar costs.

To conclude, the combination of LPT with GreedySlack shows the best performance both in terms of efficiency and stability for a reasonable cost. When the cost is an issue, the next fastest strategy with decent performance is FFI when combined with DAslack (or even GreedySlack if the cost is particularly critical).

Conclusion

This paper focuses on the problem of scheduling jobs under unavailability constraints that may occur earlier of later than expected. We derived a rule that a scheduling algorithm must respect to produce stable solutions (i.e., schedules for which the effective duration is no longer than the expected one). A collection of algorithms was proposed and assessed on simulations with actual traces. Among the studies heuristics, which all achieve stability, LPT minimizes efficiency degradation the most.

As future works, we could study other complementary mechanisms such as checkpointing and migration. Also, the stretch is an interesting metric in the context of desktop grids (where a continuous flow of jobs must be computed) and has not been considered in this work. Finally, we plan to extend our empirical investigation to new settings such as testing multiple levels of disturbance.

Annex

Symbol Definition i index of the machines j index of the jobs k index of the intervals m number of machines n number of jobs K i number of intervals on machine i K total number of intervals ( m i=1 K i ) b i cycle time of machine i p j processing cost of job j a i (k) duration of availability k on machine i u i (k) duration of unavailability k on machine i s i (k) start date of unavailability k on machine i e i (k) end date of unavailability k on machine i p max maximum execution duration (max 1≤i≤m,1≤j≤n b i p j ) a min minimum availability duration (min 1≤i≤m,1≤k≤K i a i (k)) a max maximum availability duration (max 1≤i≤m,1≤k≤K i a i (k))

Figure 2 :

 2 Figure 2: Unavailability k may start and end earlier or later due to the disturbance δ i (k).

Figure 4 :

 4 Figure 4: Induction basis for the proof of Proposition 1: initial schedule on the first line and the three cases on the following lines.

5 :

 5 π i (k) ← π i (k) ∪ {j} {Schedule job j in interval k on machine i}

Algorithm 5

 5 GreedySlackInput: a set of n jobs, a set of m machines with unavailabilities Output: an allocation function π1: for all 1 ≤ i ≤ m do {For all machines} 2:

3 :

 3 s i (k) ← e i (k){Move unavailabilities at the start of the intervals} 4:

Figure 5 :

 5 Figure 5: Horizon ratios of schedules generated with 10 sets of 10,000 jobs and 10 sets of 500 machines (100 instances). Each combination between a global and a local policy has an additional version that ignores the slack rule (left).

Figure 6 :

 6 Figure 6: Stabilities of schedules generated with 10 sets of 10,000 jobs and 10 sets of 500 machines (100 instances). Each combination between a global and a local policy has an additional version that ignores the slack rule (left).

Figure 7 :

 7 Figure 7: Execution times for generating the same schedules as in Figures 5 and 6.

  δ i (k) disturbance on unavailability start date s i (k) π i (k) set of jobs allocated to availability k on machine i C j completion time of job j in a given scheduleC max makespan (max 1≤j≤n C j ) C max highest disturbed makespan λ horizon σ stability ( Cmax λ ) M i (k)maximum size of the jobs assigned to availability k on machine i(M i (k) = max j∈π i (k) b i p j ) S i (k)sum of the sizes of the jobs assigned to availability k on machine i (S i (k) = j∈π i (k) b i p j ) d i (k) slack preceding unavailability k on machine i (a i (k) -S i (k))

Table 1 :

 1 Notation summary

RR 2014-1

FEMTO-ST Institute

The traces were provided by Michella Taufer.RR

2014-1

Acknowledgement

The authors would like to thank Grégory Mounié with whom this work was initiated.

L.-C. Canon -A. Essafi -D. Trystram

FEMTO-ST Institute


Nan-Fu Chiu
email: nfchiu@ntnu.edu.tw

Maxime Le Ster

Cheng-Du Yang

Ming-Hung Tseng

Feng-Yu Tsai

Interactions between excitation and extraction modes in an organic based plasmon-emitting diode

Keywords: surface plasmon polaritons (SPPs), surface plasmon grating coupled emissions (SPGCEs), directional emission, full width at half maximum (FWHM), plasmonic emitter, biosensors

This study demonstrates the feasibility of enhancing an organic based plasmon-emitting diode on the directional light beaming efficiency by near-field surface plasmon polaritons (SPPs) in both metal grating and polymer grating nanostructures. The interaction between organic/metal and PR/metal interfaces to cause SPPs can facilitate specific directional emission. Directional emission properties give rise to a spectral band-gap response enhancement. Our results also verify that efficient surface plasmon grating coupled emissions (SPGCEs) can improve directionality under index mediated tuning.

Experimental results indicate SP decoupling emission in the visible light. The subsequent emission intensity can increase by up to 3.5 times. Moreover, a narrow FWHM of approximately 60 nm in a defined direction is achieved, and a SP coupling rate is approximately 80% on the metal grating structure. The proposed is highly promising for use as an active plasmonic emitter and discoloration biosensors with enhanced SPPs resonance energy, owing to interactions with the organic/metal nanostructure.

Surface plasmon polaritons (SPPs) [START_REF] Wood | On a remarkable case of uneven distribution of light in a diffraction grating spectrum[END_REF][START_REF] Otto | Excitation of nonradiative surface plasma waves in silver by the method of frustrated total reflection[END_REF][START_REF] Kretschmann | The Determination of the Optical Constants of Metals by Excitation of Surface Plasmons[END_REF][START_REF] Homola | Surface plasmon resonance sensors based on diffraction gratings and prism couplers: sensitivity comparison[END_REF] are photons passing through a dielectric material and metal film surfaces causing their density to free electrons to resonate with energy transfer at the same wavevector as the coupling photon's wave. Most research in the recent decade has focused on increasing radiation efficiency [START_REF] Gifford | Extraordinary transmission of organic photoluminescence through an otherwise opaque metal layer via surface plasmon cross coupling[END_REF][START_REF] Wedge | Surface plasmon-polariton mediated light emission through thin metal films[END_REF][START_REF] Feng | Highly directional emission via coupled surfaceplasmon tunneling from electroluminescence in organic light-emitting devices[END_REF], in which surface plasmon coupled emissions (SPCE) mechanisms from fluorescent molecules by incident wave excite an evanescent field near the Kretschmann configuration [START_REF] Lakowicz | Directional surface Plasmon-coupled emission: a new method for high sensitivity detection[END_REF][START_REF] Winter | Emission of light through thin silver films via near-field coupling to surface plasmon polaritons[END_REF][START_REF] Cao | Surface Plasmon-Coupled Emission: What Can Directional Fluorescence Bring to the Analytical Sciences?[END_REF]. Recent efforts have implemented organic based plasmonic emitting diodes by using the surface plasmon grating coupled emissions (SPGCE) [START_REF] Chiu | Enhancement and tunability of active plasmonic by multilayer grating coupled emission[END_REF][START_REF] Nien | Directional photoluminescence enhancement of organic emitters via surface plasmon coupling[END_REF] to develop related design concepts and technologies for sensing applications [START_REF] Wang | Bacterial pathogen surface plasmon resonance biosensor advanced by long range surface plasmons and magnetic nanoparticle assays[END_REF][START_REF] Yeh | Use of dispersion imaging for grating-coupled surface plasmon resonance sensing of multilayer langmuir-blodgett films[END_REF][START_REF] Yuk | Highly sensitive grating coupler-based surface plasmon-coupled emission (SPCE) biosensor for immunoassay[END_REF][START_REF] Chiu | Organic-based plasmonic emitters for sensing applications[END_REF][START_REF] Chiu | Organic Plasmon-Emitting Diodes for Detecting Refractive Index Variation[END_REF]. This SPGCE brings internal dipole interaction and light extraction mechanisms on the metal nanostructures [START_REF] Koller | Organic plasmon-emitting diode[END_REF][START_REF] Chiu | Enhanced luminescence of organic/metal nanostructure for grating coupler active long-range surface plasmonic device[END_REF]. While consisting of hybrid modes of light fields and oscillating electron fields at the metal/organic material interfaces, SPGCE uses the spontaneous emission of tris-(8hydroxyquinoline) aluminum (Alq 3 ) organic semiconductor molecules to excite surface plasmon resonance (SPR) by grating coupled emission. The emissions correspond to the resonant condition of surface plasmon (SP) modes on the organic/Au interface and grating coupled to the Au/air interface for the emission of light. This light extraction passes through a metal approach to excite the evanescent wave on the periodic nanostructure, leading to a highly tunable emission property and increasing the luminescence efficiency.

This study develops different mechanisms based on SPR to compare the propagation property for the coupling effect of an electrical field and higher radiative emission rate.

While our previous studies [START_REF] Chiu | Enhancement and tunability of active plasmonic by multilayer grating coupled emission[END_REF][START_REF] Chiu | Organic Plasmon-Emitting Diodes for Detecting Refractive Index Variation[END_REF] have addressed this question, certain aspects are explored in more detail in this study, especially surface plasmon band gap (SPBG) modes associated with both the excitation and extraction interaction [START_REF] Benahmed | Bandgap-assisted surface-plasmon sensing[END_REF][START_REF] Toma | Surface plasmoncoupled emission on plasmonic Bragg gratings[END_REF]. An attempt is also made to more thoroughly elucidate the nature of all of the SPPs modes uncovered by A c c e p t e d M a n u s c r i p t examining the dispersion relation for a grating distribution at the resonance frequency for each mode. The proposed SPGCE method is highly promising for use in biosensor applications, owing to its high speed, label-free and high sensitivity capabilities with realtime reaction monitoring.

Experimental methods and theoretical models

This study has designed different plasmonic emitting devices by verifying a proposition involving the relationship between the SPR coupling effect of excitation and emission rate of extraction. In the device fabrication, the nanostructure with lamellar grating patterns is prepared by using electron-beam lithography (EBL). The grating pattern consists of 100 nm thick Au on Si-Si 3 N 4 substrate with an exposure area of 1.2×1.2 mm 2 , as shown by four devices in Fig. 1. The pattern of grating pitch size of 500 nm consists of four devices of Au-film/Au(grating) for device-1 and Au-film/PR(grating) for device-2, and Aufilm/Au(grating)/Alq 3 for device-3 and Au-film/PR(grating)/Alq 3 for device-4 structure, respectively. The device-1 and device-2 structures were without the organic Alq 3 layer.

The device-3 and device-4 structures were fabricated by thermally evaporating organic Alq 3 layer. The layer of 80 nm thick emissive Alq 3 deposited by thermal evaporation under vacuum (~10 -7 Torr) to obtain the corrugated structures of the organic thin films. The details of the fabrication process were reported in our previous work [START_REF] Chiu | Enhancement and tunability of active plasmonic by multilayer grating coupled emission[END_REF][START_REF] Chiu | Organic Plasmon-Emitting Diodes for Detecting Refractive Index Variation[END_REF].

In this system setup, an angular interrogation-based SPR sensor system is designed for /2 -mode (GWC Technologies, USA) and photoluminescence (PL) emission measurement system (Fig. 2) for angular fluorescence spectra-mode by using the designated SPGCE structure. These angle measurement systems are used to implement the SP absorption mode and SP emission mode spectra. This PL system has two kinds of light sources for a 405-nm laser diode light source (BWB-405-20E (20mW), B&W TEK Inc, USA) and a white light source (Newport Oriel Spectral Luminator 69050) used to excite A c c e p t e d M a n u s c r i p t 6 Alq 3 molecules at a fixed incident angle of 45° on the SPGCE device. A laser passes through a camera objective lens, iris diaphragms, polarizer filter and convex lenses, focuses on the device chip. Organic light emitters are pumped by laser directly, and we scan the photoluminescence from different angles. These devices are placed on a rotational stage, and a spectrum meter on the arm connected to the stage makes a revolution around the chip. The emissions of organic film on metal grating nanostructures are collected by a focal lens and analyzed by the high-resolution spectrometer (HR2000 UV-NIR, Ocean Optics Co.). The spectrometer is moved at an angle ( e ) to determine the PL intensity of that specific emission angle in order to examine the variations of top-side emitted light.

Theoretical models of grating coupled SPR (GCSPR)

Briefly, the grating coupled SPR (GCSPR) [START_REF] Romanato | Sensitivity enhancement in grating coupled surface plasmon resonance by azimuthal control[END_REF][START_REF] Tawa | Optical microscopic observation of fluorescence enhanced by grating-coupled surface plasmon resonance[END_REF] is formed by a periodically symmetrical lamellar grating, (Figs. 1(a) and 1(b)). An incident single-wavelength of TM mode plane wave is separated, upon reflection, into different orders. When the grating period is shorter than the wavelength of light, the SP wave vector (k SP ) is longer than the wave vector (k // ) of the light and can comply with the SPR conditions in Eq. (1) and Eq.

(2). These equations show the construction for the k vectors of the plane waves. The angle of reflection of m th order may be related to the angle of incidence, as obtained from Eq. (3). [START_REF] Nien | Directional photoluminescence enhancement of organic emitters via surface plasmon coupling[END_REF][START_REF] Chiu | Organic Plasmon-Emitting Diodes for Detecting Refractive Index Variation[END_REF][START_REF] Chiu | Enhanced luminescence of organic/metal nanostructure for grating coupler active long-range surface plasmonic device[END_REF]

] 2 2 0 eff m eff m sp n n k k (1) 2 sin 0 // th SP eff m k k n k ( 2
)
th i m R m th sin sin (3) || eff eff n (4)
A c c e p t e d M a n u s c r i p t

where m is the permittivity of the thin gold film; i is the angle of incidence; (m) R is the angle of reflection of m th order and depends on wavelength; is the pitch of the grating; n eff [24] is the effective complex refractive index of the grating nanostructure; is the electrical field component orthogonal to the grating period dielectric constant; and // is the electrical field component oriented parallel to the dielectric constant of the grating bars. Its behavior is observed through the excitation of surface plasmons, which are strong optical resonances based on coherent oscillations of the free electrons in the metal grating surface.

Therefore, the reflected waves consist of an infinite sum of plane waves propagating at different angles with respect to the z axis. The SPR angles depend on the wavelength of the incident wave.

The GCSPR device is based on light diffraction on a periodically modulated surface of a nanostructure. Figure 3(a) shows the SPR dispersion relationship curve for a grating coupler [START_REF] Romanato | Sensitivity enhancement in grating coupled surface plasmon resonance by azimuthal control[END_REF][START_REF] Giannattasio | Direct observation of surface plasmon-polariton dispersion[END_REF]. A vector diagram of the various wave vectors is associated with the incident wavelength, the grating, the diffracted light, and the surface plasmon. When to increase the (mth) R = i or to decrease the (mth) R becomes imaginary, k x becomes a surface evanescent wave in x axis propagation. An evanescent wave is an electromagnetic field with an imaginary momentum component in the direction z transverse to the direction of wave propagation x, and with an imaginary wavenumber kz. Since the momentum is imaginary, a photon does not propagate towards z, despite the existence of the field. Under this circumstance, the surface plasmons are excited by -1st order diffracted light. This coupling condition can be expressed as Eq. ( 5). Based on Eq. ( 5), the azimuthal angle at SP coupler occurs is given by Eq. ( 6). [START_REF] Chiu | Enhanced luminescence of organic/metal nanostructure for grating coupler active long-range surface plasmonic device[END_REF][START_REF] Romanato | Sensitivity enhancement in grating coupled surface plasmon resonance by azimuthal control[END_REF] where is an azimuthal angle, and m 1 and m 2 are the diffraction order to which the SP modes associated with them are coupled, where much of the evanescent light is confined.

cos sin 2 2 2 sin 0 2 2 2 0 2 2 i th th i eff SP k m m k n k (5)

Theoretical models of SP grating coupled emission (SPGCE)

The proposed SPGCE method is based on the fluorescent emission from the active organic layer and its diffraction in a periodically modulated surface with possible improvement of SPPs, owing to subwavelength grating of metallic thin films. Based on use of SPGCE device as a simplified model, Figs. 1(c) and 1(d) show the possible interaction mechanisms. The SPGCE method of a given surface plasmon photonic defines its optical properties, including transmission, reflection, and angular dependence. Spatial distribution of an electromagnetic field can be manipulated in a SP band-gap to improve the local field in a dielectric. Figure 3(b) shows the changes from non-radiative SPPs to radiative emission by the cross-coupling of grating nanostructure of specific direction optical properties under different diffraction orders and emission angles. According to this figure, the cross-coupled energy transfer is equivalent to near-field coupling of the dipole to SPPs modes in organic/metal interface. In the SPGCE theoretical model, at a certain wavelength, ( ) can originate from the matching momentums of the internal emission ( e ) through grating coupler condition (dielectric constant of Alq 3 and pitch size of ) to the organic/metal (k SP(organic/metal) ) dispersion curve, as shown in Eq. [START_REF] Feng | Highly directional emission via coupled surfaceplasmon tunneling from electroluminescence in organic light-emitting devices[END_REF]. Equation ( 8) is the wave-vectors parallel to the surface of the emission light. Moreover, Eq. ( 7) and Eq. [START_REF] Lakowicz | Directional surface Plasmon-coupled emission: a new method for high sensitivity detection[END_REF] give such a matching condition for the guided mode of the organic layer and the coupling of light emission. SP-coupling emission occurs when the Bragg equation satisfies the SP wave resonance, [START_REF] Lakowicz | Directional surface Plasmon-coupled emission: a new method for high sensitivity detection[END_REF] where k sp is the SP wave vector parallel to the surface of the interfaces between metal and dielectric (e.g., the organic/metal interface); metal is the permittivity of the thin gold film; and organic is the permittivity of the organic film. This property provides an effective approach for the dynamic control of light emission and absorption in SP modes. For the SPGCE theoretical model, a portion of light is propagated outwards through organic layers into the air. Therefore, Figures 1(a) and 1(b) show three wave vectors, i.e. k radiative (k rad ), k nrad-radiative (k nrad ), and k SP(metal/organic) , between different interfaces of a grating nanostructure.

Such cross-coupling includes SPs and waveguide mode across the metal film.

Results and discussion

Determination the resonance properties from the GCSPR structure

This study implements the angular interrogation method in the ( -2 ) mode of PL system for white light source. The angular modulation scheme adopts utilizes a zero order reflected configuration in which a range of angles on monochromatic light are incident onto the top side of the grating layer. The angle is scanned with a computer controlled motorized stage with a step size of 0.0025•• . The GCSPR device is placed in the center of rotation of a high resolution rotary table measuring azimuthal angle ( ). The out coupled beam is transmitted through a 2X telocentric lens, which has a working distance of 6.5 cm on a 1.2 Mega pixel Monochrome-CCD camera (The Imaging Source Europe GmbH). The camera determines coupled optical image change in ambient refraction index, leading to an observable shift of angle ( ) and intensity change in the reflectance.

Figure 4 shows the changes of angular-dependent reflectivity around resonant angle from the GCSPR device by using a TM polarized light source (PL system for white light source). The resonant peak for the grating coupler is measured on a rotary table at zero The excitation of SPGCE resonance spectra is monitored using the above angular interrogation measurement mode for PL system.

This PL system is a white light source used to excite Alq 3 molecules at different incident angles on the SPGCE device. Figure 6 shows the different incident angles at a specific resonance absorption capacity. 500 nm of the pitch size allows for the otherwise absorption SPR mode to be coupled by the SPGCE diffraction condition. The spectral position of this resonance is governed by the pitch size and shape and by the dielectric functions of both the metal and the surrounding media [START_REF] Chiu | Organic Plasmon-Emitting Diodes for Detecting Refractive Index Variation[END_REF][START_REF] Cheng | Characterization of the surface plasmon polariton band gap in an Ag/SiO2/Ag T-shaped periodical structure[END_REF][START_REF] Andrew | Energy Transfer Across a Metal Film Mediated by Surface Plasmon Polaritons[END_REF]. Organic layer Alq

Determination of the emission properties from the SPGCE structure

Using the PL method of 405-nm laser that excites SPPs enhances the radiative light and control of the directional emission. Light emission scattering is used to excite an organic layer by surface plasmon on a thin gold film support. The dispersion relation for the scattering light arises from the momentum match between the Au/Alq 3 and Au/air regions of the SPGCE device. degrees at em = 520.43nm, 540nm and, 526.7nm, while the second resonance angle for -20, -15 and -10 degrees at em = 645.7 nm, 672.3 nm and 698.6 nm, excites the -1 st order mode.

Experimental results indicate that these devices have a strong directional emission as well as enhanced intensity. A preliminary estimate is made of the pitch or wavelength of the grating required to scatter the surface plasmon mode back out to light. Above results can be calculated from the SP dispersion relation in Eqs. ( 7) and ( 8). This high directional is explained as a combination of an increased efficiency in the excitation of the organic layer and an enhanced spatial coherence, which is achieved by coupling this organic layer to extended plasmon modes in the SPGCE nanostructure, and the subsequent out-coupling to free-space radiation.

Figure 9 shows the SPGCE device resultant of improved luminescence from multiple emission angles vs. SP resonance wavelength spectrogram. Figure 9(a) clearly shows the SPP 1 (Au/Alq 3 ) coupled via a Bragg scatter of -k (-2 / ) for -1 st order dispersion relation.

To ensure that the emission is a continuous function of wavelength, this phenomenon exhibits an over coupling (without gap). The spectra of SP resonance at angle of incident =10°, 15°, 20°, 25° and 30°, respectively.

3 . 2

 32 Photoluminescence (PL) measurement for white light source is taken for the specific directional resonance spectra produced by a designated SPGCE device. This experiment was performed at Glovebox Systems for operationally high purity levels < 1 PPM of O 2 and H 2 O at room temperature. The SPGCE device can be significantly enhanced from the three mechanisms, i.e., coupled SPP from Alq 3 scattering emission, non-radiative mode, and excitation of the waveguide mode in internal metal nanostructures. This study also

  Figures 7(a) and7(b) show the different incident wavelengths (using the PL system for white light source) from 480 to 660 nm and analysis of the resonance angle characteristics.

Figure 7 (

 7 Figure 7(a) shows the different wavelength light irradiation in the device-3 nanostructure from 480 to 560 nm, in which this wave propagation ranges from 35 to 10 degrees.Obviously, the experimental results correlate well with Fig.6(b) white line (m) of -2 nd order for SPP2(Au/Alq 3 ) mode. Figure7(b) indicates that the in device-4 nanostructure has two absorption peaks in the small angle of 10~15 degrees and a large angle of 25~35 degrees, respectively. Figure6(d)shows these two absorption peaks for the propagation path that closely corresponds to the first-order curve of white line (n) of -1 st order for SPP1(Au/Alq 3 ) and (O) of -1 st order for SPP2(Au/PR) modes.

Figure 8

 8 Figure8shows the behaviors of the SPP at a metal/organic interface via coupler transfer emission for the device-3, device-4 and planar structure. A planar structure has a maximum at 530 nm and a full width at half maximum (FWHM) of 120 nm, as is expected for Alq 3 emission. The SPGCE device results in a shape angular pattern of the emission,

Figure 9 (

 9 b) shows the emission dispersion relation ( -k) at different grating pitch sizes of SPGCE devices by extracting the maximum intensities of PL spectra at different viewing angles.A c c e p t e d M a n u s c r i p t

Figure 9 (Figure 1 .

 91 Figure9(c) shows the device-4 nanostructure emission properties with a gap of 30 nm (SPBG-1). Its gap is via a Bragg scatter for -1st order to provide an SPP1(Au/Alq3) interaction between the branches scattered. The other a -k component for -1 st order to provides the SPP2(Au/PR) branches scattered on SPBG-2 of 12 nm. Figure9(d)summarizes the experimental results of dispersion relation curves for the device-4 structure at different viewing angles. The branches scattered for forward and backward traveling SP modes represent energy gap, which opens up for light at normal emission. The emission optical far-field patterns exhibit the symmetry and shape of the SP mode. The phenomenon is attributed to a metal surface plasmon mediated light out-coupling mechanism, which is also responsible for the relatively high extraction efficiency[START_REF] Benahmed | Bandgap-assisted surface-plasmon sensing[END_REF][START_REF] Toma | Surface plasmoncoupled emission on plasmonic Bragg gratings[END_REF][START_REF] Wedge | Surface plasmon-polariton mediated emission of light from top-emitting organic light-emitting diode type structures[END_REF].

Figure 2 .

 2 Figure 2. Photograph of photoluminescence (PL) emission measurement system setup (1. diode laser of wavelength 405nm, 2. reflective mirror, 3. objective lens, 4. iris diaphragms, 5. polarizer filter, 6 convex lenses, 7. rotational stage, 8. device chip and sample holder, 9.focal lens, and 10. spectrum meter).

Figure 3 .

 3 Figure 3. Surface plasmon polariton dispersion curves. (a) coupling phase definition of the GCSPR model propagating at a free metal-air interface. (b) Dispersion curve of the SPGCE model for emission phase definition, the explained that intrinsic Alq 3 emission and excitation into the Au/Alq 3 coupler SP emission angle.

Figure 4 .u s c r i p t 20 Figure 5 .

 4205 Figure 4. Measurement of the reflectance intensity vs resonance angle from the device-1 structure for (a) and device-2 structure for (b) at TM-polarized light. SP resonance angle shift at a difference azimuthal angle with incident light wavelength (c) device-1 (d) device-2 structures.

Figure 6 .

 6 Figure 6. SPGCE results of using SP-coupling to associate them with dispersion relation characteristics. Figures 6(a) and 6(c) show the SPGCE coupler on difference incident light wavelength of the resonance angle for device-3 and device-4 nanostructure, respectively.

Figures 6 (

 6 Figures 6(b) and 6(d) show 3D spectra for the incident at different wavelengths to analyze the resonance angle characteristics of device-3 and device-4 nanostructure, respectively.

Figure 7 .

 7 Figure 7. (a) device-3 structure show -1 st order field of SP energy with strong absorption curves, (b) device-4 structure show -1st and -2nd orders at Au/Alq 3 and Au/PR interfaces of SP energy absorption curves.

Figure 8 .

 8 Figure 8. PL emissions obtained from a SPGCE and planar structure use a 405-nm laser to excite an organic layer. The PL is measured on organic/metal grating. The changes in SPR are measured from the color of different angular spectra.

Figure 9 .

 9 Figure 9. Experimental measurement of the emission spectra on observation angle ( ) as shown in (a) for device-3 and (b) for device-4 structure shows 3D contour plot of PL spectra (from 430 to 800 nm) at different viewing angles (from -40° to 40°). (c) for device-3 and (d) for device-4 structure as shown in dispersion relation ( -k) with different pitch size.

Figure 1

 1 Figure 1

Figure

  Figure

  Figure 2

Figure

  Figure 3

3

 3 Figure 3

Figure

  Figure 4

4

 4 Figure 4

Figure 5

 5 Figure 5

Figure 6

 6 Figure 6

Figure

  Figure 7

7

 7 Figure 7

  Figure 8

Figure 9

 9 Figure 9

Acknowledgements

The authors would like to thank the Ministry of Science and Technology of the Republic of China, Taiwan, for financially supporting this research under Contract No. MOST 103-2221-E-003 -008, NSC 102-2221-E-003-021, and NSC 99-2218-E-003-002-MY3.

A c c e p t e d M a n u s c r i p t