**3.3 System model**

We assume that each PE is completly connected to other PEs, with non-identical processing speeds and communication bandwidths The set of PEs is expressed as *P* = {*P*1, *P*2,..., *Pm*},

when the indicative value for the schedule length is minimized. In this chapter, the indicative

33 On the Effect of Applying the Task Clustering

after *s* task merging steps and *φs* is the set of mapping between PEs and clusters after *s*

includes both task execution time and data transfer time, provided that each task is scheduled as late as possible and every data from its immediate predecessors has been arrived before the scheduled time (its start time). Table 1 shows notations and definitions for deriving

*PEs, i.e., P*1 *and P*2*. The DAG has two clusters, i.e., cls*5(1) *and cls*5(4) *after 5 task merging steps. In (a), numerical values on tasks and edges mean the time unit to be processed on the reference PE and the time unit to be transferred among reference PEs on the reference communication bandwidth. On the other hand, (b) corresponds to the state that cls*5(1) *and cls*5(4) *have been assigned to P*1 *and*

*cls*, *φs*) **and the schedule length**

processor utilization. The schedule length can not be known before scheduling every task,

to minimizing the schedule length to some extent. In this section we present that relationship

processor system, provided that every processor speed and communication bandwidth are

*slw*(*Gs*

As for Δ*sls*−1 *w*,*up*, it is defined in the literature (Kanemitsu, 2010). Furthermore, it can be proved

that the upper bound of the schedule length can be reduced by reducing *slw*(*Gs*

*cls*). In the literature (Kanemitsu, 2010), it is proved that minimizing *slw*(*Gs*

*cls*) − Δ*sls*−1 *w*,*up*

1 + 1 *gmin*

effect on the schedule length. In this section, we show that minimizing *slw*(*Gs*

between Table 2 shows notations for showing characteristics of *slw*(*Gs*

leads to minimizing the lower bound of the schedule length as follows. **Lemma 1.** *In an identical processor system, let* Δ*sls*−1 *w*,*up which satisfies slw*(*Gs*

> *sl*(*Gs cls*) ≥

1, no processor assignment policy is needed. Thus, let *slw*(*Gs*

*be derived before s task merging steps. Then we obtain*

*where cp and gmin are defined in table 2, and sl*(*Gs*

*l* ∈ *clss*(*j*). In table 1, especially *S*(*ns*

*k* which dominates *slw*(*Gs*

*P*2*, respectively. The bottom are shows the derivation process for slw*(*G*5

*process, it is shown that the schedule length may be maximized if n*5

means that the schedule length may be maximized if *ns*

for Identical Processor Utilization to Heterogeneous Systems

**Example 1.** *Fig. 1 shows one example for deriving slw*(*Gs*

*cls*, *φs*). In the table, assigned PEs for *clss*(*i*) and *clss*(*j*) are *Pp* and *Pq*, respectively. And

*k*. Threrfore, the smaller *S*(*ns*

*cls*, *φs*), that means the indicative value for the schedule length

*cls*, *φs*) is the maximum value of the execution path length which

*cls*, *φs*) (In the case of *slw*(*Gs*

*cls*, *φs*) with maintaining the certain size of each cluster for

*cls*, *φs*). Thus, it must be proved that *slw*(*Gs*

*k*, *i*) means the degree of increase of

*k* is scheduled as late as possible.

*cls*, *φs*)*(s* = 5*). In the figure, there are two*

*k*, *i*), the earlier *ns*

*cls*, *φ*5)*. From the derivation*

2 *is scheduled as late as possible.*

*cls*, *φs*) = *level*(*ns*

*k* can be

*cls*, *φs*) can

*cls*) by the

*cls*)

*cls*, *φs*) leads

*cls*, *φs*). In an identical

*cls*) − *cp* ≤ Δ*sls*−1 *w*,*up and*

*cls*, *φs*) in an identical processor

, (2)

*cls*) *is the schedule length after s task merging steps.*

*k*))

value is defined as *slw*(*Gs*

task merging steps. *slw*(*Gs*

scheduled. The task *ns*

*k* ∈ *clss*(*i*), *ns*

**4.2 Relationship between** *slw*(*Gs*

system as *slw*(*Gs*

following lemma.

Our objective is to minimize *slw*(*Gs*

we must estimate it by using *slw*(*Gs*

execution time by independent tasks for *ns*

*slw*(*Gs*

suppose *ns*

Table 1. Parameter Definition Related to *slw*(*Gs cls*) (Here *ns k* ∈ *clss*(*i*)).

and let the set of processing speeds as *alpha*, i.e., *α* = {*α*1, *α*2,..., *αm*}. Let the set of communication bandwidths as *β*, i.e.,

$$
\beta = \begin{pmatrix}
\infty & \beta\_{1,2} & \beta\_{1,3} & \dots \beta\_{1,m} \\
\beta\_{2,1} & \infty & \beta\_{2,3} & \dots \beta\_{2,m} \\
\beta\_{3,1} & \beta\_{3,2} & \infty & \dots \beta\_{3,m} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
\beta\_{m,1} & \beta\_{m,2} & \beta\_{m,3} & \dots & \infty
\end{pmatrix}.
\tag{1}
$$

*βi*,*j* means the communication bandwidth from *Pi* to *Pj*. The processing time in the case that *ns k* is processed on *Pi* is expressed as *tp*(*ns k*, *αi*) = *w*(*ns k*)/*αi*. The data transfer time of *es k*,*l* over *βi*,*j* is *tc*(*es i*,*j* , *βk*,*l*) = *c*(*es i*,*j* )/*βk*,*l*. This means that both processing time and data transfer time are not changed with time, and suppose that data transfer time within one PE is negligible.

#### **4. Processor utilization**

#### **4.1 The indicative value for the schedule length**

The schedule length depends on many factors, i.e., execution time for each task, communication time for each data exchanged among tasks, execution order after the task scheduling, processing speed, and communication bandwidth. Furthermore, whether a data transfer time can be localized or not depends on the cluster structure. The proposed method is that a cluster is generated after the lower bound of the cluster size (the total execution time of every task included in the cluster) has been derived. The lower bound is decided 4 Will-be-set-by-IN-TECH

*l* ∈/ *clss*(*i*)

*l* ∈/ *clss*(*i*)

*l* ∈/ *clss*(*i*)

*l* ∈/ *clss*(*i*)

, *αp*) − ∑*ns*

�

*k*, *αp*) + *tc*(*es*

�

�

�

�

*l* ∈ *clss*(*i*)}∪{*ns*

*l*∈*desc*(*ns*

, *αp*) + *tc*(*el*,*k*, *βq*,*p*)

*tlevel*(*ns k*) �

*k*,*l*

*k*) + *blevel*(*ns*

*ns k*∈*clss*(*i*)

*cls*) (Here *ns*

*k*, *i*) + *blevel*(*ns*

{*LVs*(*i*)}

∪ {*START Tasks* ∈ *clss*(*i*)}.

∪ {*START Tasks* ∈ *clss*(*i*)}.

∪ {*END Tasks* ∈ *clss*(*i*)}.

∪ {*END Tasks* ∈ *clss*(*i*)}.

*l*) �

. (1)

*k*,*l* over

*k*)/*αi*. The data transfer time of *es*

*k* ∈ *tops*(*i*).

*k*}

� , *if ns*

*k* ,*i*) *tp*(*ns l* , *αp*)

, *βp*,*q*) + *blevel*(*ns*

*k*) �

*k*)

*k* ∈ *clss*(*i*)).

⎞

⎟⎟⎟⎟⎟⎠

)/*βk*,*l*. This means that both processing time and data transfer time

� *level*(*ns k*) �

*k*)*s*.*t*., *ns*

*k*)*s*.*t*., *ns*

*k*)*s*.*t*., *ns*

*k*),*s*.*t*., *ns*

*l*

*k*∈*tops*(*i*)

� *S*(*ns*

*clss*(*i*)∈*Vs cls*

and let the set of processing speeds as *alpha*, i.e., *α* = {*α*1, *α*2,..., *αm*}. Let the set of

∞ *β*1,2 *β*1,3 ... *β*1,*m β*2,1 ∞ *β*2,3 ... *β*2,*m β*3,1 *β*3,2 ∞ ... *β*3,*m*

*βm*,1 *βm*,2 *βm*,3 ... ∞

*βi*,*j* means the communication bandwidth from *Pi* to *Pj*. The processing time in the case that

are not changed with time, and suppose that data transfer time within one PE is negligible.

The schedule length depends on many factors, i.e., execution time for each task, communication time for each data exchanged among tasks, execution order after the task scheduling, processing speed, and communication bandwidth. Furthermore, whether a data transfer time can be localized or not depends on the cluster structure. The proposed method is that a cluster is generated after the lower bound of the cluster size (the total execution time of every task included in the cluster) has been derived. The lower bound is decided

*k*, *αi*) = *w*(*ns*

*l*) + *tp*(*ns l*

*l* |*ns k* ≺ *ns l* , *ns*

*k*, *i*), *otherwise*.

*k*∈*outs*(*i*)

*φs* {..., *< clss*(*i*), *Pp >*,... }

*l*∈*clss*(*i*) *tp*(*ns*

*tlevel*(*ns*

Parameter Definition

*l* ∈ *pred*(*ns*

*l* ∈ *pred*(*ns*

*l* ∈ *suc*(*ns*

*l* ∈ *suc*(*ns*

*tops*(*i*) �

*ins*(*i*) �

*outs*(*i*) �

*btms*(*i*) �

*desc*(*ns*

*S*(*ns*

*tlevel*(*ns k*)

*blevel*(*ns*

*level*(*ns*

*slw*(*Gs*

*ns*

*βi*,*j* is *tc*(*es*

*i*,*j*

**4. Processor utilization**

*ns k*|∀*ns*

*ns k*|∃*ns*

*ns k*|∃*ns*

*ns k*|∀*ns*

*k*, *i*) ∑*ns*

� max *ns l*∈*pred*(*ns k* ) �

*k*) max *ns*

*BLs*(*i*) max *ns*

Table 1.  In this chapter, the indicative value is defined as *slw*(*Gs cls*, *φs*), that means the indicative value for the schedule length after *s* task merging steps and *φs* is the set of mapping between PEs and clusters after *s* task merging steps. *slw*(*Gs cls*, *φs*) is the maximum value of the execution path length which includes both task execution time and data transfer time, provided that each task is scheduled as late as possible and every data from its immediate predecessors has been arrived before the scheduled time (its start time). Table 1 shows notations and definitions for deriving *slw*(*Gs cls*, *φs*). In the table, assigned PEs for *clss*(*i*) and *clss*(*j*) are *Pp* and *Pq*, respectively. And suppose *ns k* ∈ *clss*(*i*), *ns l* ∈ *clss*(*j*). In table 1, especially *S*(*ns k*, *i*) means the degree of increase of execution time by independent tasks for *ns k*. Threrfore, the smaller *S*(*ns k*, *i*), the earlier *ns k* can be scheduled. The task *ns k* which dominates *slw*(*Gs cls*, *φs*) (In the case of *slw*(*Gs cls*, *φs*) = *level*(*ns k*)) means that the schedule length may be maximized if *ns k* is scheduled as late as possible.

**Example 1.** *Fig. 1 shows one example for deriving slw*(*Gs cls*, *φs*)*(s* = 5*). In the figure, there are two PEs, i.e., P*1 *and P*2*. The DAG has two clusters, i.e., cls*5(1) *and cls*5(4) *after 5 task merging steps. In (a), numerical values on tasks and edges mean the time unit to be processed on the reference PE and the time unit to be transferred among reference PEs on the reference communication bandwidth. On the other hand, (b) corresponds to the state that cls*5(1) *and cls*5(4) *have been assigned to P*1 *and P*2*, respectively. The bottom are shows the derivation process for slw*(*G*5 *cls*, *φ*5)*. From the derivation process, it is shown that the schedule length may be maximized if n*5 2 *is scheduled as late as possible.*

#### **4.2 Relationship between** *slw*(*Gs cls*, *φs*) **and the schedule length**

Our objective is to minimize *slw*(*Gs cls*, *φs*) with maintaining the certain size of each cluster for processor utilization. The schedule length can not be known before scheduling every task, we must estimate it by using *slw*(*Gs cls*, *φs*). Thus, it must be proved that *slw*(*Gs cls*, *φs*) can effect on the schedule length. In this section, we show that minimizing *slw*(*Gs cls*, *φs*) leads to minimizing the schedule length to some extent. In this section we present that relationship between Table 2 shows notations for showing characteristics of *slw*(*Gs cls*, *φs*). In an identical processor system, provided that every processor speed and communication bandwidth are 1, no processor assignment policy is needed. Thus, let *slw*(*Gs cls*, *φs*) in an identical processor system as *slw*(*Gs cls*). In the literature (Kanemitsu, 2010), it is proved that minimizing *slw*(*Gs cls*) leads to minimizing the lower bound of the schedule length as follows.

**Lemma 1.** *In an identical processor system, let* Δ*sls*−1 *w*,*up which satisfies slw*(*Gs cls*) − *cp* ≤ Δ*sls*−1 *w*,*up and be derived before s task merging steps. Then we obtain*

$$sl(G\_{cls}^s) \ge \frac{sl\_{w}(G\_{cls}^s) - \Delta sl\_{w,up}^{s-1}}{1 + \frac{1}{\mathcal{G}\_{min}}},\tag{2}$$

*where cp and gmin are defined in table 2, and sl*(*Gs cls*) *is the schedule length after s task merging steps.*

As for Δ*sls*−1 *w*,*up*, it is defined in the literature (Kanemitsu, 2010). Furthermore, it can be proved that the upper bound of the schedule length can be reduced by reducing *slw*(*Gs cls*) by the following lemma.

*Proof.* In *seq*≺

Also, only in the case of *sl*(*GS*

− max *p*∈*G*0 *cls*

for Identical Processor Utilization to Heterogeneous Systems

*slw*(*GS*

⇔ − max *p*∈*G*0 *cls*

⇔ *sl*(*GS*

can be minimized if *slw*(*Gcls*) is minimized.

As a next step, we show the relationship between *slw*(*Gs*

**Lemma 3.** In an identical processor system, we have

⎧ ⎪⎪⎪⎨

⎪⎪⎪⎩

*n*0 *k* ,*n*0 *l* ∈*p*, *n*0 *k*∈*pred*(*n*0 *l* )

*cls*) − *cp* ≤ *slw*(*GS*

∑

⎧ ⎪⎪⎪⎨

⎪⎪⎪⎩

*n*0 *k* ,*n*0 *l* ∈*p*, *n*0 *k*∈*pred*(*n*0 *l* )

*cls*) ≤ *slw*(*GS*

∑

in *seq*≺

2007).

following corollary.

proved.

*the table 2. Then we have*

*s* , some edges are localized and others may be not localized. Furthermore, edges

≤ *slw*(*GS*

*cls*)

≤ *slw*(*GS*

∑

*cls*) − *sl*(*GS*

*c*(*e* 0 *k*,*l* ) *cls*)

. (5)

⎫ ⎪⎪⎪⎬

⎪⎪⎪⎭

*cls*, *φs*) and the schedule length in a

*cls*). (6)

*cls*, *φs*). (7)

*cls*) − *cp*. (4)

*s* do not always belong to the critical path. Then we have the following relationship.

35 On the Effect of Applying the Task Clustering

⎫ ⎪⎪⎪⎬

⎪⎪⎪⎭

*cls*) ≤ *cp*, we have the following rlationship.

⎫ ⎪⎪⎪⎬

⎪⎪⎪⎭

⎧ ⎪⎪⎪⎨

⎪⎪⎪⎩

*n*0 *k* ,*n*0 *l* ∈*p*, *n*0 *k*∈*pred*(*n*0 *l* )

*cls*) − *sl*(*GS*

*c*(*e* 0 *k*,*l* )

*cls*) + max *p*∈*G*0 *cls*

From lemma 1 and 2, it is concluded that in an identical processor system the schedule length

heterogeneous distributed system. The following lemma is proved in the literature (Sinnen,

In a heterogeneous distributed system, we assume the state like fig. 2, i.e., at the initial state every task is assigned a processor with the fastest and the widest communication bandwidth (let the processor as *Pmax*). In fig. 2 (a), each task belongs to respective processor. Furthermore, we virtually assign *Pmax* to each task to decide the processing time for each task and the data transfer time among any two tasks. Let the mapping as *φ*0. Under the situation, we have the

**Corollary 1.** *In a heterogeneous distributed system, let cpw*(*φ*0) *as the one with the mapping φ*0 *in*

As for the relationship between *cp* and *cpw*, in the literature (Sinnen, 2007), the following is

*cpw*(*φ*0) ≤ *sl*(*Gs*

*cpw* ≤ *sl*(*Gs*

*c*(*e* 0 *k*,*l* )

Fig. 1. Example of *slw*(*G*5 *cls*, *φ*5) derivation.

**Lemma 2.** *In an identical processor system, if sl*(*GS cls*) ≤ *cp, then we obtain*

$$\text{lsf}(\mathbf{G}\_{cls}^{\mathbf{S}}) \le sl\_w(\mathbf{G}\_{cls}^{\mathbf{S}}) + \max\_{p \in \mathbf{G}\_{cls}^{\mathbf{0}}} \left\{ \sum\_{\substack{n\_k^0, n\_l^0 \in p\_\succ\\n\_k^0 \in pred(n\_l^0)}} c(e\_{k,l}^0) \right\} \cdot \text{l.} \tag{3}$$

6 Will-be-set-by-IN-TECH

(a) After 5 tesk merging steps have been done. (b) After processor assignments have been done.

5 cls (1)

5 n2

5 5 4

> 5 4

level(n ) = 22, tlev

blevel(n ) = 1, level(n ) = 12.5,

> 5 k 5

5

*cls*) ≤ *cp, then we obtain*

*c*(*e* 0 *k*,*l* )

⎫ ⎪⎪⎪⎬

⎪⎪⎪⎭

∑

∈

6 5 p4

5 5 5 7 5 p4 p6

5 kk n out (4) 5 5 4 4

BL (4) = max {S(n ,4) + blevel(n )} = S(n ,4) + blevel(n ) = 0 +13.5 13.5, LV (4) = TL (4) + BL (4) = level(n ) 8.

5 55 4

5 1 n

5 3 n

 5 4 n

5

5 5 5 5 4 p4 5 6

5 5

5 5 w cls 55 5 2

sl (G , ) = max{LV (1),LV (4)} = LV (1) = level(n ) = 25. φ

el(n ) = TL (4) + t (n ) + t (n ) = 8.5 + 0.5 + 2.5 = 11.5,

5

= =

5 +13.5 = 22.

. (3)

5 5 n 5 cls (4)

5 6 n

5 7 n 5 cls (4)

assign

2 p 1 1 p 3 1 p 5 1

e , ) + blevel(n ) 1.5 0 1 10 1 13.5,

*c*

=

ααα

+ =

= + ++ +=

5 1 ),

*cls*) + max *p*∈*G*0 *cls*

⎧ ⎪⎪⎪⎨

⎪⎪⎪⎩

*n*0 *k* ,*n*0 *l* ∈*p*, *n*0 *k*∈*pred*(*n*0 *l* )

β

) +S(n ,1) = 0 + t (n , ) + t (n , ) + t (n , ) = 3,

5 n6

5 7 n

P1 P2 1,2 β = 0.5 2,1 β = 2

α1 = 4 α2 = 2

tlevel(n ) = TL (1 5 555

blevel(n ) = t (n ) + t (e , ) + blevel(n ) = 1+ 20 +1 = 22,

β

tlevel(n ) = TL (1) +S(n ,1) = 0 + t (n ) + t (n ) = 0.5 1 1.5,

5 5 5 55 5 1 p1 2 3 1,4 1,2 4

blevel(n ) = t (n ) + max{blevel(n ),blevel(n ), t (e , ) + blevel(n )}

5 2

(n ) = 25.

*cls*, *φ*5) derivation.

*cls*) ≤ *slw*(*GS*

5 5 5 15 4 5 5 5 5 5 15 5 47

top (1) = {n }, top (4) = {n }, in (1) = {n ,n },in (4) = {n ,n } out (1) = {n ,n ,n }, out (4) = {n ,n } btm (1) = {n ,n }, btm (4) = {n } - - - - - - cls (1) section- - - - - - TL (1) = tlevel(n ) = 0,

5 5 5 1 5 2 5

> 5 2

level(n ) = 25,

level(n ) 15, S(n ,1) = 0,

5 5 3 p3

blevel(n ) t (n ) + t (

=

5 k 5

5

Fig. 1. Example of *slw*(*G*5

∈

blevel(n ) = 4 + 5 + 2 = 12, level(n ) = 15,

> 5 kk n out (1) 5 5 2 2 5 55

BL (1) = max {S(n ,1) + blevel(n )} = S(n ,1) + blevel(n ) = 25, LV (1) = TL (1) + BL (1) = level

555 5 5 5 125 5 47 5 5 5 5 25 5 7

> 5 55 5 2 p2 2,7 1,2 7

*c*

*c*

5 55 5 35 3 p1 p2

= 5 5 3,5 1,2 5

β

= 0.5 + max{22, 13.5, 8 +13.5} = 22.5 level(n

5 5

**Lemma 2.** *In an identical processor system, if sl*(*GS*

*sl*(*GS*

5 55 5 5 55 5 p1 p2 p3

tlevel(n ) = TL (1) +S(n ,1) = 0 + t (n ) + t (n ) + t (n ) = 3,

5 5 n 5 4 n

5 1 n

5 cls (1)

assign

5 2 n 5 n3 *Proof.* In *seq*≺ *s* , some edges are localized and others may be not localized. Furthermore, edges in *seq*≺ *s* do not always belong to the critical path. Then we have the following relationship.

$$-\max\_{p \in G\_{cls}^0} \left\{ \sum\_{\substack{n\_k^0, n\_l^0 \in p, \\ n\_k^0 \in p \text{red}(n\_l^0)}} c(e\_{k,l}^0) \right\} \le sl\_w(G\_{cls}^S) - cp. \tag{4}$$

Also, only in the case of *sl*(*GS cls*) ≤ *cp*, we have the following rlationship.

$$\begin{split} sl\_{w}(\mathbf{G}\_{\mathrm{cls}}^{\mathcal{S}}) - cp &\leq sl\_{w}(\mathbf{G}\_{\mathrm{cls}}^{\mathcal{S}}) - sl(\mathbf{G}\_{\mathrm{cls}}^{\mathcal{S}}) \\ \Leftrightarrow & - \max\_{p \in \mathcal{C}\_{\mathrm{cls}}^{0}} \left\{ \sum\_{\begin{subarray}{c} n\_{l}^{0}, n\_{l}^{0} \in \mathcal{P}, \\ n\_{k}^{0} \in prrd(n\_{l}^{0}) \end{subarray}} c(\boldsymbol{e}\_{k,l}^{0}) \right\} \leq sl\_{w}(\mathbf{G}\_{\mathrm{cls}}^{\mathcal{S}}) - sl(\mathbf{G}\_{\mathrm{cls}}^{\mathcal{S}}) \\ \Leftrightarrow & sl(\mathbf{G}\_{\mathrm{cls}}^{\mathcal{S}}) \leq sl\_{w}(\mathbf{G}\_{\mathrm{cls}}^{\mathcal{S}}) + \max\_{p \in \mathcal{C}\_{\mathrm{cls}}^{0}} \left\{ \sum\_{\begin{subarray}{c} n\_{k}^{0}, n\_{l}^{0} \in \mathcal{P}, \\ n\_{k}^{0} \in prrd(n\_{l}^{0}) \end{subarray}} c(\boldsymbol{e}\_{k,l}^{0}) \right\}. \end{split} \tag{5}$$

From lemma 1 and 2, it is concluded that in an identical processor system the schedule length can be minimized if *slw*(*Gcls*) is minimized.

As a next step, we show the relationship between *slw*(*Gs cls*, *φs*) and the schedule length in a heterogeneous distributed system. The following lemma is proved in the literature (Sinnen, 2007).

**Lemma 3.** In an identical processor system, we have

$$c p\_{\overline{w}} \le s! (G\_{cls}^s). \mathbf{I} \tag{6}$$

In a heterogeneous distributed system, we assume the state like fig. 2, i.e., at the initial state every task is assigned a processor with the fastest and the widest communication bandwidth (let the processor as *Pmax*). In fig. 2 (a), each task belongs to respective processor. Furthermore, we virtually assign *Pmax* to each task to decide the processing time for each task and the data transfer time among any two tasks. Let the mapping as *φ*0. Under the situation, we have the following corollary.

**Corollary 1.** *In a heterogeneous distributed system, let cpw*(*φ*0) *as the one with the mapping φ*0 *in the table 2. Then we have*

$$\text{lcp}\_w(\phi\_0) \le \text{sl}(G\_{\text{cls}}^s, \phi\_\text{s}).\text{L} \tag{7}$$

As for the relationship between *cp* and *cpw*, in the literature (Sinnen, 2007), the following is proved.

**Lemma 4.** *In an identical processor system, by using gmin defined in table 2, we have*

By using lemma 4, in a heterogeneous distributed system, the following is derived.

*cpw*(*φ*0) ≤ *cpw*(*φs*) ≤ *sl*(*Gs*

**Thorem 4.1.** *In a heterogeneous distributed system, let the DAG after s task merging steps as Gs*

*slw*(*Gs*

1 *gmin*(*φ*0)

1 *gmin*(*φ*0)

1 + 1 *gmin*(*φ*0)

Assume that Δ*sls*−1 *w*,*up* is the value which is decided after *s* − 1 task merging steps. Since

*cp*(*φ*0) = *slw*(*G*0

1 *gmin*

37 On the Effect of Applying the Task Clustering

1 *gmin*(*φs*) *cls is assigned to a processor in P. Let the schedule length as sl*(*Gs*

*cls*, *φs*) − Δ*sls*−1 *w*,*up*

1 + 1 *gmin*(*φ*0)

 *sl*(*Gs*

*cls*, *φs*) − Δ*sls*−1 *w*,*up*

⇔ (14)

*cls*, *φs*) − *cp*(*φ*0) ≤ Δ*sls*−1 *w*,*up, the following relationship is*

*cpw*. (8)

*cpw*(*φs*). (9)

*cls*, *φs*). (10)

. (11)

*cpw*(*φ*0) ≤ Δ*sls*−1 *w*,*up*. (12)

*cls*, *φs*) ≤ Δ*sls*−1 *w*,*up* (13)

. (15)

*cls*, *φ*0), (16)

*cls*, *φs*). Thus if this is applied to (12), we

*cls.*

*cls*, *φs*)*.*

*cp* ≤ 1 +

> 1 +

**Corollary 2.** *In a heterogeneous distributed system, we have*

for Identical Processor Utilization to Heterogeneous Systems

**Corollary 3.** *In a heterogeneous distributed system, we have*

From corollary 2 and 3, the following theorem is derived.

*sl*(*Gs*

*cls*, *φs*) −

*cls*, *φs*) −

*cls*, *φs*) ≥

*Proof.* From the assumption and corollary 2, we have

*slw*(*Gs*

Also, from corollary 3, we obtain *cpw*(*φ*0) ≤ *sl*(*Gs*

*slw*(*Gs*

*sl*(*Gs*

*cls*, *φs*) ≥

 1 +

 1 +

*slw*(*Gs*

From corollary 1, the following is derived.

*And assume every cluster in Vs*

*derived.*

have

*If we define* Δ*sls*−1 *w*,*up that satisfies slw*(*Gs*

*cp*(*φs*) ≤

Fig. 2. Assumed condition during cluster generation procedures.

Table 2. Parameter Definitions which are used in analysis on *slw*(*Gs cls*, *φs*). 8 Will-be-set-by-IN-TECH

0 1 n

0 cls (5) 0 cls (6)

Pmax

0 cls 0 (a) Initial state (DAG : G , Assignment : ). φ

Fig. 2. Assumed condition during cluster generation procedures.

*n*0

*k*) The processor to which *ns*

*k*, *αp*) + ∑ *es k*,*l* ∈*p*

> *n*0 *k*∈*V*0 *cls*

> *n*0 *k*∈*V*0 *cls*

Table 2. Parameter Definitions which are used in analysis on *slw*(*Gs*

Parameter Definition

by which a sequence *< n*0

Pmax

3 n 0 4 n

0 cls (1)

0 cls (3)

0 2 n 0

Pmax

{ } i i cpu speed max α ∈α

*p* One path of *G*0

*cp* max

*tp*(*ns*

*cpw* max

*cpw*(*φs*) max

*g*min min

*g*max max

*seq*≺

*seq*≺

*proc*(*ns*

*cp*(*φs*) max

*p*

� ∑ *ns k*∈*p*

assign

0 cls (2)

assign

max P1 P2 P

i,j bandwidth max i,j β ∈β = β

2,..., *n*0

*k*) + ∑ *e*0 *k*,*l* ∈*p c*(*es k*,*l* ) ⎫ ⎬ ⎭ .

�

*w*(*n*0 *k* ) � .

*tp*(*ns k*, *αp*) �

> min *n*0 *l* ∈*suc*(*n*0 *k* ) {*w*(*n*0 *l* )}

> max *n*0 *l* ∈*suc*(*n*0 *k* ) {*c*(*e*0 *k*,*l* )}

> max *n*0 *l* ∈*suc*(*n*0 *k* ) {*w*(*n*0 *l* )}

> min *n*0 *l* ∈*suc*(*n*0 *k* ) {*c*(*e*0 *k*,*l* )}

5 1 n

3 n 5 4 n

> 5 6 n 5 5 n

5 cls (4)

5 7 n

5

cls 5 (b) The state after task clustering (DAG : G , Assignment : ). φ

*k*}∪{*e*0

0,1,*e*0

*k >* is constructed, where *e*0

*k* is an END task.

*k* has been assigned.

*k*, *ns*

⎫ ⎪⎬

⎪⎭ .

⎫ ⎪⎬

⎪⎭ .

*cls*, *φs*).

, where *ns*

1,2,...*e*0

*k*−1,*k*},

*l* are assigned to *Pp*, *Pq*.

*l*−1,*l* ∈ *E*0,

*s* .

assign assign

5 2 n 5

5 cls (1)

0 6 n 0 5 n

0 cls (4)

0 7 n

Pmax

Pmax

*cls*, i.e., {*n*0

0, *n*0 1, *n*0

*s* One path in which every task belongs to *seqs*.

⎧ ⎨ ⎩ ∑ *n*0 *k*∈*p*

*tc*(*c*(*es k*,*l* ), *βp*,*q*)

> *p*∈*G*0 *cls*

*p*∈*Gs cls*

min *n*0 *j* ∈*pred*(*n*0 *k* ) � *w*(*n*0 *j* ) �

max *n*0 *j* ∈*pred*(*n*0 *k* ) � *c*(*e*0 *j*,*k* ) � ,

max *n*0 *j* ∈*pred*(*n*0 *k* ) � *w*(*n*0 *j* ) �

min *n*0 *j* ∈*pred*(*n*0 *k* ) � *c*(*e*0 *j*,*k* ) � ,

⎧ ⎪⎨

⎪⎩

⎧ ⎪⎨

⎪⎩

*p*

0, *n*0 1, *n*0

0 is a START task and *n*0

*s* (*i*) Set of subpaths in each of which every task in *clss*(*i*) belongs to *seq*≺

2,..., *n*0

*w*(*ns*

� ∑ *n*0 *k*∈*p*

� ∑ *ns k*∈*p*

= α { }

**Lemma 4.** *In an identical processor system, by using gmin defined in table 2, we have*

$$cp \le \left(1 + \frac{1}{\mathcal{g}\_{\min}}\right) cp\_{\text{w.}} \mathbf{L} \tag{8}$$

By using lemma 4, in a heterogeneous distributed system, the following is derived.

**Corollary 2.** *In a heterogeneous distributed system, we have*

$$ccp(\phi\_s) \le \left(1 + \frac{1}{g\_{min}(\phi\_s)}\right) cp\_w(\phi\_s).\blacksquare \tag{9}$$

From corollary 1, the following is derived.

**Corollary 3.** *In a heterogeneous distributed system, we have*

$$c p\_w(\phi\_0) \le c p\_w(\phi\_s) \le s l(\mathbb{G}\_{cls}^s \phi\_s). \mathbf{L} \tag{10}$$

From corollary 2 and 3, the following theorem is derived.

**Thorem 4.1.** *In a heterogeneous distributed system, let the DAG after s task merging steps as Gs cls. And assume every cluster in Vs cls is assigned to a processor in P. Let the schedule length as sl*(*Gs cls*, *φs*)*. If we define* Δ*sls*−1 *w*,*up that satisfies slw*(*Gs cls*, *φs*) − *cp*(*φ*0) ≤ Δ*sls*−1 *w*,*up, the following relationship is derived.*

$$\text{scl}(G\_{cls}^{\text{s}}\phi\_{\text{s}}) \ge \frac{s l\_{\text{w}}(G\_{cls}^{\text{s}}\phi\_{\text{s}}) - \Delta s l\_{\text{w},\mu p}^{\text{s}-1}}{1 + \frac{1}{g\_{\text{min}}(\phi\_{\text{0}})}}.\tag{11}$$

*Proof.* From the assumption and corollary 2, we have

$$\operatorname{ssl}\_{w}(G\_{\operatorname{cls}^{s}}^{\operatorname{s}}\phi\_{\operatorname{s}}) - \left(1 + \frac{1}{g\_{\operatorname{min}}(\phi\_{\operatorname{0}})}\right) \operatorname{cp}\_{w}(\phi\_{\operatorname{0}}) \leq \operatorname{ssl}\_{w,\operatorname{\mu}p}^{\operatorname{s}-1}.\tag{12}$$

Also, from corollary 3, we obtain *cpw*(*φ*0) ≤ *sl*(*Gs cls*, *φs*). Thus if this is applied to (12), we have

$$slw(\mathcal{G}\_{cls}^{s}, \phi\_{\mathbb{S}}) - \left(1 + \frac{1}{\mathcal{g}\_{min}(\phi\_{0})}\right) sl(\mathcal{G}\_{cls}^{s}, \phi\_{\mathbb{S}}) \le \Delta sl\_{w, up}^{s-1} \tag{13}$$

⇔ (14)

$$\text{lsl}(G\_{cls}^s, \phi\_{\mathbb{S}}) \ge \frac{\text{sl}\_{\text{w}}(G\_{cls}^s, \phi\_{\mathbb{S}}) - \Delta \text{sl}\_{\text{w}, \text{up}}^{s-1}}{1 + \frac{1}{\mathcal{G}\_{\text{min}}(\phi\_{\mathbb{S}})}}. \tag{15}$$

Assume that Δ*sls*−1 *w*,*up* is the value which is decided after *s* − 1 task merging steps. Since

$$\exp(\phi\_0) = s l\_w(G\_{\rm cls'}^0 \phi\_0),\tag{16}$$

this value is an upper bound of increase in terms of *slw*(*Gs cls*, *φs*) and can be defined in any policy, e.g., the slowest processor is assigned to each cluster and so on. However, at least Δ*sls*−1 *w*,*up* must be decided before *s* task merging steps. From the theorem, it can be said that reducing *slw*(*Gs cls*, *φs*) leads to reduction of the lower bound of the schedule length in a heterogeneous distributed system.

As for the upper bound of the schedule length, the following theorem is derived.

**Thorem 4.2.** *In a heterogeneous distributed sytem, if and only if sl*(*Gs cls*, *φs*) ≤ *cp*(*φ*0) = *sl*(*G*0 *cls*, *φ*0)*, we have*

$$\text{sl}(\mathcal{G}\_{\text{cls}'}^{s}\phi\_{\text{s}}) \le \text{sl}\_{\text{w}}(\mathcal{G}\_{\text{cls}'}^{s}\phi\_{\text{s}}) + \mathbb{J} - \lambda - \mu,\tag{17}$$

If *sl*(*Gs*

*cls*, *φs*) ≤ *cp*(*φ*0) = *sl*(*G*0

objective of our proposal is to minimize *slw*(*Gs*

**4.3 The lower bound of each cluster size**

*cls*, *φ*0), we obtain

*cls*, *φR*) ≤ *slw*(*GR*

reduction of the schedule length in a heterogeneous distributed system. Thus, the first

39 On the Effect of Applying the Task Clustering

because this value does not guarantee each cluster size. Thus, in this section we present how large each cluster size should be. In the literature (Kanemitsu, 2010), the lower bound of each

> ⎧ ⎪⎨

max *n*0 *l* ∈*V*0 *cls* � *w*(*n*0 *l* ) �

*g*max

⎫ ⎪⎬

⎪⎭

*l* , max *αi*∈*α* {*αi*})

*g*max(*φ*0)

⎪⎩

every cluster size is above a certain threshold, *δ*. And *R* corresponds to the number of merging steps when every cluster size is *δopt* or more. If taking the initial state of the DAG in a

> ⎧ ⎪⎪⎪⎨

max *n*0 *l* ∈*V*0 � *tp*(*n*0

*cls*, *φs*) can not always be minimized by *δopt*(*φ*0), because the mapping of each

⎪⎪⎪⎩

this chapter, one heuristic of our method is to impose the same lower bound (*δopt*(*φ*0)) for

In the previous section, we presented how large each cluster size should be set for processor utilization. In this section, we present the task clustering algorithm with incorporating the

*cls*, *φs*).

*cls*, *φR*) − *sl*(*GR*

*cls*, *φR*) (22)

*cls*, *φs*) ≤ *sl*(*Gs*−1

*cls*, *φs*) minimization" not enough,

. (24)

. (25)

*cls*, *φ*0). In

*cls*) can be minimized, provided that

�

*cls*, *φs*) is not equal to *slw*(*G*0

⎫ ⎪⎪⎪⎬

⎪⎪⎪⎭

*cls*, *φ*0) can be minimized. However,

*cls* , *φs*−1).

*cls*, *φs*) leads to the

*cls*, *φR*) + *ζ* − *λ* − *μ*. (23)

−*ζ* + *λ* + *μ* ≤ *slw*(*GR*

Theorem 4.2 is true if we adopt a clustering policy such that *sl*(*Gs*

From theorem 4.1 and 4.2, it can be concluded that reducing the *slw*(*Gs*

⇔ *sl*(*GR*

for Identical Processor Utilization to Heterogeneous Systems

To achieve processor utilization, satisfying only "*slw*(*Gs*

*δopt* =

(24) is the lower bound of each cluster size when *slw*(*GR*

��������

By imposing *δopt*(*φ*0), it can be said that at least *slw*(*G*0

cluster and each processor is changed and then *slw*(*Gs*

every cluster which will be generated by the task clustering.

*δopt*(*φ*0) =

for *s* ≥ 1 *slw*(*Gs*

**5. Task clustering algorithm**

**5.1 Overview of the algorithm**

following two requirements.

1. Every cluster size is *δopt*(*φ*0) or more.

cluster size in an identical processor system is derived as follows.

������*cpw* max *n*0 *k*∈*V*0

heterogeneous system into account, *δopt* is expressed by *δopt*(*φ*0) as follows.

*cpw*(*φ*0) max *n*0 *l* ∈*V*0

*where*

$$\zeta = \max\_{p} \left\{ \sum\_{\substack{n\_{\ell}^{0}, n\_{\ell}^{0} \in p\_{\ell} \\ n\_{\ell}^{0} \in pred(n\_{\ell}^{0}), \\ t\_{\ell} \left( \boldsymbol{e}\_{i,\ell}^{0} \max\_{\boldsymbol{\beta}\_{i,\ell} \in \hat{\boldsymbol{\beta}}} \{ \boldsymbol{\beta}\_{i,\ell} \} \right) = 0}} \boldsymbol{t}\_{\ell} \left( \boldsymbol{e}\_{k,\ell}^{0} \max\_{\boldsymbol{\beta}\_{i,\ell} \in \hat{\boldsymbol{\beta}}} \left\{ \boldsymbol{\beta}\_{i,\ell} \right\} \right) \right\},\tag{18}$$

$$\lambda = \min\_{p} \left\{ \sum\_{\substack{n\_k^0 \in p\_r \\ p \text{cov}(n\_k^s) = p\_m}} \left( t\_p(n\_{k'}^s \mathbf{a}\_m) - t\_p(n\_{k'}^0 \max\_{a\_i \in \mathfrak{a}} \{ \mathbf{a}\_i \}) \right) \right\}, \tag{19}$$

$$\mu = \min\_{p} \left\{ \sum\_{\substack{n\_k^0, n\_l^0 \in p, \operatorname{proc}(n\_k^s) = P\_{l\_\cdot} \\ \operatorname{proc}(n\_l^s) = P\_{l'} \\ \operatorname{proc}(n\_l^s) = P\_{l'} \\ n\_k^0 \in \operatorname{proc}(n\_l^0)}} \left( t\_\mathfrak{c}(e\_{k,l'}^s \beta\_{l,j}) - t\_\mathfrak{c}(e\_{k,l'}^0 \max\_{\beta\_{l,j} \in \beta} \left\{ \beta\_{l,j} \right\}) \right) \right\}. \tag{20}$$

*p and proc*(*n*0 *k* ) *are defined in table 2. That is, ζ*, *λ*, *μ is derived by scanning every path in the DAG.*

*Proof.* After *s* task merging steps, there may be both localized edges and not localized edges which compose *slw*(*Gs cls*, *φs*). Obviously, we have *slw*(*G*0 *cls*, *φ*0) = *cp*(*φ*0), such edges are not always ones which belongs to *cp*(*φ*0). Therefore the lower bound of *slw*(*Gs cls*, *φs*) − *cp*(*φ*0) can be derived by three factors, i.e., decrease of the data transfer time by localization in one path, increase of the processing time by task merging steps (from *φ*0 to *φs*), and increase of data transfer time for each unlocalized edges (from *φ*0 to *φs*). The localized data transfer time is derived by taking the sum of localized data transfer time for one path. On the other hand, if increase of the processing time is derived by taking the minimum of the sum of increase of task processing time from *φ*0 to *φs* for each path, this value is *λ* or more. The unlocalized data transfer time is expressed as *μ*. Then we have

$$-\mathcal{L} + \lambda + \mu \le sl\_{\mathcal{W}}(G\_{cls}^s, \phi\_s) - \varepsilon p(\phi\_0). \tag{21}$$

If *sl*(*Gs cls*, *φs*) ≤ *cp*(*φ*0) = *sl*(*G*0 *cls*, *φ*0), we obtain

10 Will-be-set-by-IN-TECH

policy, e.g., the slowest processor is assigned to each cluster and so on. However, at least Δ*sls*−1 *w*,*up* must be decided before *s* task merging steps. From the theorem, it can be said

**Thorem 4.2.** *In a heterogeneous distributed sytem, if and only if*

As for the upper bound of the schedule length, the following theorem is derived.

*cls*, *φs*) ≤ *slw*(*Gs*

*tc*(*e* 0 *k*,*l* , max *βi*,*j*∈*β*

*k*, *αm*) − *tp*(*n*0

*cls*, *φ*0)*, we have*

*sl*(*Gs*

∑

{*βi*,*j*})=0

� *tp*(*ns*

*k* )=*Pi*,

*cls*, *φs*). Obviously, we have *slw*(*G*0

always ones which belongs to *cp*(*φ*0). Therefore the lower bound of *slw*(*Gs*

− *ζ* + *λ* + *μ* ≤ *slw*(*Gs*

� *tc*(*e s k*,*l*

*cls*, *φs*) leads to reduction of the lower bound of the schedule length in

� *βi*,*j* � )

⎫

⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬

⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭

� ⎫ ⎪⎪⎪⎬

⎪⎪⎪⎭

� *βi*,*j* � ) �

*k* , max *αi*∈*α* {*αi*})

> 0 *k*,*l* , max *βi*,*j*∈*β*

, *βi*,*j*) − *tc*(*e*

*k* ) *are defined in table 2. That is, ζ*, *λ*, *μ is derived by scanning every path in the DAG.*

*Proof.* After *s* task merging steps, there may be both localized edges and not localized edges

be derived by three factors, i.e., decrease of the data transfer time by localization in one path, increase of the processing time by task merging steps (from *φ*0 to *φs*), and increase of data transfer time for each unlocalized edges (from *φ*0 to *φs*). The localized data transfer time is derived by taking the sum of localized data transfer time for one path. On the other hand, if increase of the processing time is derived by taking the minimum of the sum of increase of task processing time from *φ*0 to *φs* for each path, this value is *λ* or more. The unlocalized data

*cls*, *φs*) and can be defined in any

, (18)

, (19)

. (20)

*cls*, *φs*) − *cp*(*φ*0) can

⎫ ⎪⎪⎪⎪⎪⎪⎬

⎪⎪⎪⎪⎪⎪⎭

*cls*, *φ*0) = *cp*(*φ*0), such edges are not

*cls*, *φs*) − *cp*(*φ*0). (21)

*cls*, *φs*) + *ζ* − *λ* − *μ*, (17)

this value is an upper bound of increase in terms of *slw*(*Gs*

that reducing *slw*(*Gs*

*sl*(*Gs*

*where*

a heterogeneous distributed system.

*cls*, *φs*) ≤ *cp*(*φ*0) = *sl*(*G*0

*ζ* = max *p*

*λ* = min *p*

*μ* = min *p*

*p and proc*(*n*0

which compose *slw*(*Gs*

⎧

⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨

⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩

⎧ ⎪⎪⎪⎨

⎪⎪⎪⎩

⎧ ⎪⎪⎪⎪⎪⎪⎨

⎪⎪⎪⎪⎪⎪⎩

transfer time is expressed as *μ*. Then we have

*n*0 *k* ,*n*0

*n*0 *k*∈*p*, *proc*(*ns k* )=*pm*

*n*0 *k* ,*n*0 *l* ∈*p*, *n*0 *k*∈*pred*(*n*0 *l* ),

*tc* (*es k*,*l* ,max *βi*,*j*∈*β*

∑

∑

*l* ∈*p*,*proc*(*ns*

*proc*(*ns l*)=*Pj*,

*n*0 *k*∈*pred*(*n*0 *l* )

$$-\mathcal{L} + \lambda + \mu \le sl\_w(G\_{cls}^R, \phi\_R) - sl(G\_{cls}^R, \phi\_R) \tag{22}$$

$$\Leftrightarrow \text{sl}(\mathbb{G}\_{\text{cls}}^{\mathbb{R}}, \phi\_{\mathbb{R}}) \leq \text{sl}\_{w}(\mathbb{G}\_{\text{cls}}^{\mathbb{R}}, \phi\_{\mathbb{R}}) + \zeta - \lambda - \mu. \tag{23}$$

Theorem 4.2 is true if we adopt a clustering policy such that *sl*(*Gs cls*, *φs*) ≤ *sl*(*Gs*−1 *cls* , *φs*−1). From theorem 4.1 and 4.2, it can be concluded that reducing the *slw*(*Gs cls*, *φs*) leads to the reduction of the schedule length in a heterogeneous distributed system. Thus, the first objective of our proposal is to minimize *slw*(*Gs cls*, *φs*).

#### **4.3 The lower bound of each cluster size**

To achieve processor utilization, satisfying only "*slw*(*Gs cls*, *φs*) minimization" not enough, because this value does not guarantee each cluster size. Thus, in this section we present how large each cluster size should be. In the literature (Kanemitsu, 2010), the lower bound of each cluster size in an identical processor system is derived as follows.

$$\delta\_{opt} = \sqrt{c p\_{\text{w}} \max\_{n\_l^0 \in V\_0} \left\{ \frac{\max\_l \left\{ w(n\_l^0) \right\}}{s\_l^0} \right\}} \,\,\,\,\, \text{g}\,\,\,\tag{24}$$

(24) is the lower bound of each cluster size when *slw*(*GR cls*) can be minimized, provided that every cluster size is above a certain threshold, *δ*. And *R* corresponds to the number of merging steps when every cluster size is *δopt* or more. If taking the initial state of the DAG in a heterogeneous system into account, *δopt* is expressed by *δopt*(*φ*0) as follows.

$$\delta\_{opt}(\phi\_0) = \sqrt{\alpha\_w(\phi\_0) \max\_{n\_i^0 \in V\_0} \left\{ \frac{\max\_{n\_i^0 \in V\_0} \left\{ t\_p(n\_{1'}^0 \max\_{n\_i \in \mathcal{a}} \{n\_i\}) \right\}}{\mathcal{g}\_{\max}(\phi\_0)} \right\}}\,\tag{25}$$

By imposing *δopt*(*φ*0), it can be said that at least *slw*(*G*0 *cls*, *φ*0) can be minimized. However, for *s* ≥ 1 *slw*(*Gs cls*, *φs*) can not always be minimized by *δopt*(*φ*0), because the mapping of each cluster and each processor is changed and then *slw*(*Gs cls*, *φs*) is not equal to *slw*(*G*0 *cls*, *φ*0). In this chapter, one heuristic of our method is to impose the same lower bound (*δopt*(*φ*0)) for every cluster which will be generated by the task clustering.

#### **5. Task clustering algorithm**

#### **5.1 Overview of the algorithm**

In the previous section, we presented how large each cluster size should be set for processor utilization. In this section, we present the task clustering algorithm with incorporating the following two requirements.

1. Every cluster size is *δopt*(*φ*0) or more.

**INPUT:** *G*0

*cls* **OUTPUT:** *GR*

For each *nk* ∈ *V*, let *n*0

8. **ENDWHILE** 9. **ENDWHILE** 10. **RETURN** *GR*

*cls*

Set the mapping *φ*0 to the input DAG.

5. **WHILE** size of *pivots < δopt*(*φ*0) **DO** 6. *targets* ← *getTarget*(*pivots*);

*cls*;

**5.3 Selection for** *pivots* **and** *targets*

contribute to minimize *slw*(*GR*

**5.4 Merging** *pivots* **and** *targets*

the next merging step.

**6. Experiments**

is selected as *target*2. similarly in (c) *n*3

dominate *slw*(*Gs*

*slw*(*Gs*

Fig. 3. Procedures for the Task Clustering.

the new *pivot*4 for generating the new cluster.

*cls*, *φs*) and then *slw*(*Gs*+1

having the maximum *LV* value in *RDY*2 is selected. Then *n*2

0. Derive *δopt*(*φ*0) by eq. (25). 1. *E*0 ← *E*, *UEX*0 ← *V*0

2. **WHILE** *UEXs* �= ∅ **DO** 3. select a processor *Pp* from *P*; 4. *pivots* ← *getPivot*(*RDYs*);

Define *UEXs* as a set of clusters whose size is under *δopt*(*φ*0); Define *RDYs* as a set of clusters which statisies eq. (26).;

for Identical Processor Utilization to Heterogeneous Systems

*k* ← *nk*, *cls*0(*k*) = {*n*0

7. *RDYs*+1 ← *merging*(*pivots*, *targets*) and update *pivots*;

As mentioned in 5.1, one objective of the algorithm is to minimize *slw*(*GR*

After *pivots* and *targets* have been selected, the merging procedure, i.e.,

*cls*, *RDY*0 ← {*cls*0(*k*)|*cls*0(*k*) = {*n*0

exceeds *δopt*(*φ*0), the mapping is changed i.e., clusters in *UEX*4 are assigned to *Pmax* to select

*RDYs*, *pivots* should have maximum *LV* value (defined in table 1), because such a cluster may

i.e., *targets* should be the cluster which dominates *LV* value of *pivots*. In fig. 4 (b), *cls*2(3)

is performed. This procedure means that every cluster in *targets* is included in *pivots*+1. Then *pivots* and *targets* are removed from *UEXs* and *RDYs*. After this merging step has been performed, clusters satisfying requirements for *RDYs*+1(in eq. (26)) are included in *RDYs*+1. Furthermore, every cluster's *LV* value is updated for selecting *pivots*+1 and *targets*+1 before

We conducted the experimental simulation to confirm advantages of our proposal. Thus, we

compared with other conventional methods in terms of the following points of view.

*cls*, *φs*). Our heuristic behined the algorithm is that this policy for selecting *pivots* can

*k*} and put *cls*0(*k*) into *V*0

41 On the Effect of Applying the Task Clustering

*cls*.

*k* ) = ∅};

*cls* , *φs*+1) after *s* + 1 th merging may became lower than

5, i.e., *cls*3(5) dominating *LV*3(3) is selected as *target*3.

*pivots*+1 ← *pivots* ∪ *targets* (27)

*cls*, *φR*). The same requirement holds to the selection of *targets*,

*cls*, *φR*). Therefore, in

6, i.e., *cls*2(6) dominating *LV*2(3)

*k*}, *pred*(*n*0

2. Minimize *slw*(*GR cls*, *φR*), where *R* is the total number of merging steps until the first requirement is satisfied.

Fig. 3 shows the task clustering algorithm. At first, the mapping *φ*0 is applied to every task. Then *δopt*(*φ*0) is derived. Before the main procedures, two sets are defined, i.e., *UEXs* and *RDYs*. *UEXs* is the set of clusters whose size is smaller than *δopt*(*φ*0), and *RDYs* is defined as follow.

$$\begin{split} \text{RDY}\_{\text{s}} &= \{ \text{cls}\_{\text{s}}(r) | \text{cls}\_{\text{s}}(r) \in \text{UEX}\_{\text{s}}, \text{pred}(n\_{r'}^{\text{s}}) = \bigotimes\_{r'} \text{cls}\_{\text{s}}(r) = \{ n\_{r'}^{\text{s}} \} \} \\ &\cup \left\{ \begin{aligned} \text{cls}\_{\text{s}}(r) | \text{cls}\_{\text{s}}(r) \in \text{UEX}\_{\text{s}}, \text{cls}\_{\text{s}}(q) \notin \text{UEX}\_{\text{s}} \\ n\_{q'}^{\text{s}} \in \text{cls}\_{\text{s}}(q), n\_{q'}^{\text{s}} \in \text{pred}(n\_{r'}^{\text{s}}) \text{ for } \forall n\_{r'}^{\text{s}} \in \text{top}\_{\text{s}}(r) \end{aligned} \right\}. \end{split} \tag{26}$$

*RDYs* is the set of clusters whose preceding cluster sizes are *δopt*(*φ*0) or more. That is, the algorithm tries to merge each cluster in top-to-bottom manner.

The algorithm is proceeded during *UEXs* �= ∅, which implies that at least one cluster in *UEXs* exists. At line 3, one processor is selected by a processor selection method, e.g., by CHP(C. Boeres, 2004) (In this chapter, we do not present processor selection methods). At line 4, one cluster is selected as *pivots*, which corresponds to "the first cluster for merging". Once the *pivots* is selected, "the second cluster for merging", i.e., *targets* is needed. Thus, during line 5 to 7, procedures for selecting *targets* and merging *pivots* and *targets* are performed. After those procedures, at line 7 *RDYs* is updated to become *RDYs*+1, and *pivots* is also updated to become *pivots*+1. Procedures at line 6 and 7 are repeated until the size of *pivots* is *δopt*(*φ*0) or more. The algorithm in fig. 3 has common parts with that of the literature (Kanemitsu, 2010), i.e., both algorithms use *pivots* and *targets* for merging two clusters until the size of *pivots* exceeds a lower bound of the cluster size. However, one difference among them is that the algorithm in fig. 3 keeps the same *pivots* during merging steps until its size exceeds *δopt*(*φ*0), while the algorithm in (Kanemitsu, 2010) selects the new *pivots* in every merging step. The reason of keeping the same *pivots* is to reduce the time complexity in selection for *pivots*, which requires scanning every cluster in *RDYs*. As a result, the number of scanning *RDYs* can be reduced with compared to that of (Kanemitsu, 2010).

#### **5.2 Processor assignment**

In the algorithm presented in fig. 3, the processor assignment is performed before selecting *pivots*. Suppose that a processor *Pp* is selected before the *s* + 1th merging step. Then we assume that *Pp* is assigned to every cluster to which *Pmax* is assigned, i.e., no actual processor has been assigned. By doing that, we assume that such unassigned clusters are assigned to "an identical processor system by *Pp*" in order to select *pivots*. Fig. 4 shows an example of the algorithm. In the figure, (a) is the state of *φ*2, in which the size of *cls*2(1) is *δopt*(*φ*0) or more. Thus, *RDY*2 = *cls*2(3) = *n*2 3 , *cls*2(4) = *n*2 4 , *cls*2(7) = *n*2 7 . The communication bandwidth from *P*1 to *Pmax* is set as *min* 1≤*q*≤m,1�=*q β*1,*q* in order to regard communication

bandwidth between an actual processor and *Pmax* bottleneck in the schedule length. In (b), it is assumed that every cluster in *UEX*2 is assigned to *Pp* after *Pp* is selected. Bandwidths among *Pp* are set as *min* 1≤*q*≤m,*p*�=*q βp*,*q* to estimate the *slw*(*G*2 *cls*, *φ*2) of the worst case. Therefore, *pivot*2(in this case, *cls*2(3)) is selected by deriving *LV* value for each cluster in *RDY*2, provided that such a mapping state. After (b), if the size of *cls*3(3) is smaller than *δopt*(*φ*0), every cluster in *UEX*3 is still assigned to *Pp* to maintain the mapping state. In (d) if the size of *cls*4(3) 12 Will-be-set-by-IN-TECH

Fig. 3 shows the task clustering algorithm. At first, the mapping *φ*0 is applied to every task. Then *δopt*(*φ*0) is derived. Before the main procedures, two sets are defined, i.e., *UEXs* and *RDYs*. *UEXs* is the set of clusters whose size is smaller than *δopt*(*φ*0), and *RDYs* is defined as

*clss*(*r*)|*clss*(*r*) ∈ *UEXs*, *clss*(*q*) ∈/ *UEXs*,

*RDYs* is the set of clusters whose preceding cluster sizes are *δopt*(*φ*0) or more. That is, the

The algorithm is proceeded during *UEXs* �= ∅, which implies that at least one cluster in *UEXs* exists. At line 3, one processor is selected by a processor selection method, e.g., by CHP(C. Boeres, 2004) (In this chapter, we do not present processor selection methods). At line 4, one cluster is selected as *pivots*, which corresponds to "the first cluster for merging". Once the *pivots* is selected, "the second cluster for merging", i.e., *targets* is needed. Thus, during line 5 to 7, procedures for selecting *targets* and merging *pivots* and *targets* are performed. After those procedures, at line 7 *RDYs* is updated to become *RDYs*+1, and *pivots* is also updated to become *pivots*+1. Procedures at line 6 and 7 are repeated until the size of *pivots* is *δopt*(*φ*0) or more. The algorithm in fig. 3 has common parts with that of the literature (Kanemitsu, 2010), i.e., both algorithms use *pivots* and *targets* for merging two clusters until the size of *pivots* exceeds a lower bound of the cluster size. However, one difference among them is that the algorithm in fig. 3 keeps the same *pivots* during merging steps until its size exceeds *δopt*(*φ*0), while the algorithm in (Kanemitsu, 2010) selects the new *pivots* in every merging step. The reason of keeping the same *pivots* is to reduce the time complexity in selection for *pivots*, which requires scanning every cluster in *RDYs*. As a result, the number of scanning *RDYs* can

In the algorithm presented in fig. 3, the processor assignment is performed before selecting *pivots*. Suppose that a processor *Pp* is selected before the *s* + 1th merging step. Then we assume that *Pp* is assigned to every cluster to which *Pmax* is assigned, i.e., no actual processor has been assigned. By doing that, we assume that such unassigned clusters are assigned to "an identical processor system by *Pp*" in order to select *pivots*. Fig. 4 shows an example of the algorithm. In the figure, (a) is the state of *φ*2, in which the size of *cls*2(1) is *δopt*(*φ*0) or

, *cls*2(4) =

1≤*q*≤m,1�=*q*

bandwidth between an actual processor and *Pmax* bottleneck in the schedule length. In (b), it is assumed that every cluster in *UEX*2 is assigned to *Pp* after *Pp* is selected. Bandwidths

to estimate the *slw*(*G*2

*pivot*2(in this case, *cls*2(3)) is selected by deriving *LV* value for each cluster in *RDY*2, provided that such a mapping state. After (b), if the size of *cls*3(3) is smaller than *δopt*(*φ*0), every cluster in *UEX*3 is still assigned to *Pp* to maintain the mapping state. In (d) if the size of *cls*4(3)

*n*2 4

 *β*1,*q*

, *cls*2(7) =

*n*2 7

in order to regard communication

*cls*, *φ*2) of the worst case. Therefore,

. The communication

*q*� ∈ *pred*(*ns*

*RDYs* = {*clss*(*r*)|*clss*(*r*) ∈ *UEXs*, *pred*(*ns*

*q*� ∈ *clss*(*q*), *ns*

∪

*ns*

be reduced with compared to that of (Kanemitsu, 2010).

*cls*2(3) =

 *βp*,*q*

bandwidth from *P*1 to *Pmax* is set as *min*

1≤*q*≤m,*p*�=*q*

*n*2 3

**5.2 Processor assignment**

more. Thus, *RDY*2 =

among *Pp* are set as *min*

algorithm tries to merge each cluster in top-to-bottom manner.

*cls*, *φR*), where *R* is the total number of merging steps until the first

*r*�) *f or* ∀*ns*

*r*�) = ∅, *clss*(*r*) = {*ns*

*r*� ∈ *tops*(*r*)

*r*� }}

. (26)

2. Minimize *slw*(*GR*

follow.

requirement is satisfied.

```
INPUT: G0
         cls
OUTPUT: GR
           cls
Set the mapping φ0 to the input DAG.
Define UEXs as a set of clusters whose size is under δopt(φ0);
Define RDYs as a set of clusters which statisies eq. (26).;
For each nk ∈ V, let n0
                    k ← nk, cls0(k) = {n0
                                       k} and put cls0(k) into V0
                                                              cls.
0. Derive δopt(φ0) by eq. (25).
1. E0 ← E, UEX0 ← V0
                       cls, RDY0 ← {cls0(k)|cls0(k) = {n0
                                                       k}, pred(n0
                                                                k ) = ∅};
2. WHILE UEXs �= ∅ DO
3. select a processor Pp from P;
4. pivots ← getPivot(RDYs);
5. WHILE size of pivots < δopt(φ0) DO
6. targets ← getTarget(pivots);
7. RDYs+1 ← merging(pivots, targets) and update pivots;
8. ENDWHILE
9. ENDWHILE
10. RETURN GR
                cls;
```
Fig. 3. Procedures for the Task Clustering.

exceeds *δopt*(*φ*0), the mapping is changed i.e., clusters in *UEX*4 are assigned to *Pmax* to select the new *pivot*4 for generating the new cluster.


Olive Cultivation

*Edited by Taner Yonar*

Published in London, United Kingdom

Olive Cultivation http://dx.doi.org/10.5772/intechopen.98132 Edited by Taner Yonar

#### Contributors

Theofilos Frangopoulos, Stefano Grego, Giora Ben-Ari, Iris Biton, Dvora Namdar, Yair Mani, Fatemeh Rahimianfar, El Hassan Sakar, Said Gharby, Annette Bongartz, Martin Popp, Richard Retsch, Dietrich Oberg, Karima Bouhafa, Valentina Giovenzana, Alessia Pampuri, Roberto Beghi, Andrea Casson, Riccardo Guidetti, Alessio Tugnolo

#### © The Editor(s) and the Author(s) 2022

The rights of the editor(s) and the author(s) have been asserted in accordance with the Copyright, Designs and Patents Act 1988. All rights to the book as a whole are reserved by INTECHOPEN LIMITED. The book as a whole (compilation) cannot be reproduced, distributed or used for commercial or non-commercial purposes without INTECHOPEN LIMITED's written permission. Enquiries concerning the use of the book should be directed to INTECHOPEN LIMITED rights and permissions department (permissions@intechopen.com).

Violations are liable to prosecution under the governing Copyright Law.

Individual chapters of this publication are distributed under the terms of the Creative Commons Attribution 3.0 Unported License which permits commercial use, distribution and reproduction of the individual chapters, provided the original author(s) and source publication are appropriately acknowledged. If so indicated, certain images may not be included under the Creative Commons license. In such cases users will need to obtain permission from the license holder to reproduce the material. More details and guidelines concerning content reuse and adaptation can be found at http://www.intechopen.com/copyright-policy.html.

#### Notice

Statements and opinions expressed in the chapters are these of the individual contributors and not necessarily those of the editors or publisher. No responsibility is accepted for the accuracy of information contained in the published chapters. The publisher assumes no responsibility for any damage or injury to persons or property arising out of the use of any materials, instructions, methods or ideas contained in the book.

First published in London, United Kingdom, 2022 by IntechOpen IntechOpen is the global imprint of INTECHOPEN LIMITED, registered in England and Wales, registration number: 11086078, 5 Princes Gate Court, London, SW7 2QJ, United Kingdom

British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library

Additional hard and PDF copies can be obtained from<EMAIL_ADDRESS>
Olive Cultivation Edited by Taner Yonar p. cm. Print ISBN 978-1-80355-441-9 Online ISBN 978-1-80355-442-6 eBook (PDF) ISBN 978-1-80355-443-3


**3. Domoic Acid and Related Compounds**

#### *3.1. Discovery, Structure, and Some Properties*

Domoic acid (DA) **3** was first found and isolated from the red alga *Chondria armata* by Japanese scientists in the 1960s [37]. After three years of studies, its structure was determined and then refined through organic synthesis. Like kainic acid, **3** is a derivative of dicarboxylated pyrrolidine containing glutamate moiety, but in its another moiety, domoic acid bears octadienoic substituent derived from a monoterpenoid acid (Figure 1). Closely related metabolites, isodomoic acids **48**–**55**, were identified for more than 25 subsequent years in the red alga *C. armata* and contaminated mussels [38–40], as reviewed in [41,42]. All these metabolites, including isodomoic acids A-H along with domoilactones and some related compounds, also contain a glutamic acid residue and should be considered as effectors of GARs. However, as a rule, their effect is much weaker (Table 1). The number of known analogues of DA has increased, particularly in recent years [43].

**Table 1.** Metabolites related to domoic acid.

KARs, μM = displacement of kainic acid from the complex with kainate receptors.

Several compounds related to domoic acid (dainic acids) have recently been described and named as 7- -methyl-isodomoic acid A (**56**), 7- -methyl-isodomoic acid B (**57**), 7- -hydroxymethyl-isodomoic A (**58**), and 7- -hydroxymethyl-isodomoic acid B (**59**). Closely related minor metabolites **60**, **61**, which do not contain pyrrolidine ring, have also been isolated from the same alga *C. armata* (Figure 4) [43].

**Figure 4.** Dainic acids (**56**–**59**) and related metabolites (**60**,**61**) from *C. armata*.

The main turn in the fate of domoic acid and related compounds occurred after the discovery that these metabolites are produced not only by several species of red algae, but also by planktonic diatoms [43]. As a result of subsequent transfer of domoic acid (DA) (**3**) up the food chain from microalgae into edible mollusks [44–46], it may cause the so-called Amnesic Shellfish Poisoning (ASP) in humans that consume edible mollusks contaminated by DA [47–49]. The first case of ASP was described in 1987 from Canada, where 107 people, who had consumed cultivated mussel *Mytilus edulis*, showed symptoms of this disease and three of them died [45]. The diatom *Pseudo-nitzshia multiseries* was identified as a phytoplanktonic producer of DA, which also produces isodomoic acids E and F. Since 1987, it was found that this toxin and related compounds are responsible not only for human poisoning, but also for numerous cases of poisoning and mortality of birds and marine mammals [46–49].

Symptoms of ASP in humans include gastrointestinal alterations (abdominal cramp, nausea, vomiting), and/or neurological disorders (dizziness, short-term memory loss, seizure, epilepsy or coma in the acute cases) [47]. DA binds to glutamate receptors in the central nervous system (CNS) and myocardium [50] causing overexcitation and, as a consequence, neuro-excitatory behavior in humans, marine mammals, and fish [51–55]. The binding of DA to kainate or AMPA (α-amino-3-hydroxy-5-methyl-4-isoxazolepropionic acid) receptors, subclasses of glutamate receptors, results in the intracellular accumulation of Ca2+ [47,55]. In contrast to glutamic acid, DA causes long-lasting depolarization, neuronal swelling induced by intraneuronal accumulation of excess Ca2+, production of reactive oxygen species, DNA and mitochondrial damages, energy depletion, and cell death [55,56]. Along with the CNS, the heart is often also considered as a potential target site for adverse effects of DA. DA-induced cardiotoxicity has been confirmed not only in people suffering from ASP, but also in sea lions and zebrafish that died as a result of DA-poisoning [51,52].

Isodomoic acids (iso-DAs), which have an insecticidal effect against the American cockroach *Periplaneta americana* [38], were also isolated from marine diatoms including *P. australis*, *P. seriata*, and *Nitzschia navis-varingica* [57]. Some diatom species (e.g., *Nitzschia navis-varingica*) produce isodomoic acids A and B as the major toxin components [49]. However, iso-DAs are often present in the environment at lower concentration than DA [57]. The affinity of iso-DAs to the glutamate receptors is lower than that of DA (Table 1) [58]. Therefore, parent toxin is a major threat for humans and animals, in contrast to iso-DAs [59].

Thus, a series of DA isomers have been identified, while data on occurrence of DA and epidomoic acid (referred to as total DAs) and their toxicity have been used to establish the current regulation limits for DA of ≤20 mg·kg−1 [54]. The discovery that exposure to low levels of DA leads to long-lasting neurological effects in mammalian species [53] may suggest the need to reduce its permissible level in tissues of consumed finfish and shellfish [57].

#### *3.2. Synthesis*

Synthesis of the domoic acid **3** and correction of the earlier proposed geometry of the double bonds in its side chain have been carried out [60]. The bicyclic core was constructed from the compound **62**, obtained by multistep synthesis from **1** and diene **63** using the thermic Diels-Alder reaction to give bicyclic adduct **64** with *cis*-fused ring junction. This adduct was ozonized, treated with diazomethane and 2-methyl-2-ethyl-1,3-dioxolane in the presence of p-TsOH and yielded 1,3-dioxolane **65**. The employment of borane-dimethylsulfide complex reduced the carbonyl group. Deprotection of the silyl ester and subsequent oxidation of intermediate diol with pyridinium dichromate (PDC) provided the diester **66**. Selective removal of ketal group by 60% AcOH gave the aldehyde **67**. The Wittig reaction led to **68**, the subsequent reaction with PhSeCl to the selenium-containing aldehyde **69**. The key conversions of this synthesis consisted in the obtaining of *trans*- and *cis*-enal systems from **69**. For example, the treatment with *N*-bromosuccinimide (NBS) in tetrahydrofuran and then with NaOAc led to *cis*-enal **70** as a major product. Transformation of this particular compound, but not its trans-isomer by the Wittig reaction followed by the Jones oxidation gave the product **71**. The subsequent removal of protective groups converted it into domoic acid **3**, thus confirming the *E,Z,R*-configurations in the side chain of this toxin (Scheme 8).

**Scheme 8.** Synthesis of domoic acid.

#### *3.3. Biosynthesis, Producers, Biological Action, and Environmental Role*

Several attempts were made to study the process of biosynthesis of this toxin in order to understand how and why environmental factors trigger the biosynthesis leading to high levels of DA accumulated in diatoms. Using feeding experiments, Savage et al. [61] established that DA arises as a result of condensation of geranyl diphosphate (**72**) with glutamate. Labeled by a stable isotope (deuterium), geranyl diphosphate was incorporated from culture medium into DA that was confirmed by gas

chromatography–mass spectrometry (GC-MS). It was suggested that the condensation of geranyl diphosphate with amino group glutamic acid occurred via nucleophilic substitution of the diphosphate group with the amino group of glutamic acid (**1**).

A recent publication in Science [62] provided new important data concerning the DA biosynthesis. It was shown that these genetically programmed biosynthetic pathways are encoded by a four-gene cluster which is involved in this biosynthesis and exists in genomes of toxic microalgae belonging to the genus *Pseudo-nitzschia*. In the conditions of phosphate limitation and elevated CO2 level, probably characteristic of the final stage of microalgal bloom, *Pseudo-nitzschia* spp. express a series of enzymes involved in construction of the pyrrolidine skeleton system of DA. The up-regulation of CYP450 gene, encoding an enzyme which is responsible for the formation of 7- -carboxylic acid from geranyl diphosphate **72** at its reaction with glutamic acid (**1**), was revealed. It was shown that this gene is clustered with several other genes of DA biosynthesis (the so-called dab genes). The DA biosynthetic gene cluster was established to consist of terpene cyclase (dabA), hypothetical protein Hypo (dabB), dioxygenase (dabC), CYP450 (dabD), and probably other genes. The expression of recombinant dabA without *N*-terminal transit peptide in *E. coli* and its use as a catalyst in the reaction between **72** and glutamic acid **1** confirmed this enzyme to catalyze *N*-geranylation of l-glutamic acid in Mg2+-dependent manner. This is the first and key stage in the DA biosynthesis, which yields *N*-geranyl-l-glutamic acid **61**, as was earlier suggested by Savage et al. [61]. The use of recombinant dabC in the presence of Fe3+, oxygen, and l-ascorbic acid, and α-ketoglutarate-dependent dioxygenase, or both dabC and dabD in one put, gave one of so-called dainic acids (**56**) with a non-oxidized geranyl side chain. When the primary product of this biosynthesis **61** was incubated with *Saccharamyses cerevisae* microsomes, which expressed the transmembrane dabD, *N*-geranyl-l-glutamic acid in the presence of Fe3+ and oxygen was converted into small, but reproductible amounts of 7- -carboxy-*N*-geranyl-l-glutamic acid (**73**) and its 7- -hydroxy analog. Both products were identified by being compared with synthetic fractions. The product **73,** in the same conditions as were used for the transformation of **61** into **56**, was converted into an isomer of domoic acid **48**. However, no isomerase activity necessary for the conversion of **48** into the end product of this biosynthesis was found (Scheme 9). All the above results show that this biosynthesis pathway begins with the dab A-catalyzed geranylation of l-glutamic acid in chloroplasts. Therefore, the presence of dab genes is a character that allows the recognition of toxic strains of this genus. It can help identify environmental conditions, which may potentially cause neurotoxicity in microalgae and in their consumers such as mollusks and diatom-feeding invertebrates.

**Scheme 9.** Biosynthesis of domoic acid.

Thus, it has been confirmed that DA, as a potent excitatory amino acid, is produced primarily by *Pseudo-nitzschia* and *Nitzschia* diatoms distributed across the world and is naturally accumulated in filter-feeding marine organisms. Although many *Pseudo-nitzschia* species have the potential ability to produce this neurotoxin [49], *P. multiseries*, *P. seriata*, and *P. australis* were established as the most toxic species [57].

There have been numerous bloom events caused by highly toxic DA-producing microalgae along the USA and Canadian coasts over the past 15 years. In many cases, it led to mass poisoning of marine mammals and birds [48]. For instance, in the spring of 2015, an unusually intense and long-lasting toxigenic bloom of *Pseudo-nitzschia* microalgae associated with an abnormal warming of water, was observed in a vast area from California to Alaska. Besides the mass poisoning of marine animals, it caused significant economic losses due to the closure of farms that cultivated bivalves and crabs [63]. Thus, DA exposure has become more widespread due to the higher intensity of toxigenic *Pseudo-nitzschia* blooms and related consumption of DA-contaminated mollusks.

A suggestion can be made that the isomerase activity necessary for the transformation of less active biosynthetic precursors into DA may be present not only in these microalgae but also in consumers, or in symbionts and/or epiphytic microorganisms. It is possible that bacteria play an important role in accumulation of DA in microalgae, but the details of this are still elusive [47]. It was established that axenic diatom cultures produce less DA than xenic ones and that bacteria can enhance DA production [64]. It was shown, for example, that after the addition of the gamma-proteobacterium *Alteromonas macleodii*, isolated from the Russian clone of *P. multiseries*, to an axenic culture of another clone of this species, the amount of DA produced by the latter significantly increased [65]. The stimulating effect of bacteria on the DA production has also been found for another known DA-producer, *Nitzschia* sp. [66]. However, mechanisms of bacteria's influence on intracellular DA levels in microalgae remain insufficiently studied [49].

There are a few other hypotheses that discuss environmental factors influencing toxicity of diatoms. It was suggested that DA production may arise as a defense against grazing. However, the effect of predatory copepods on toxicity of microalgae has not been definitively confirmed [67]. The hypothesis that DA may be involved in a high-affinity iron uptake system seems likely [68]. Trick et al. [69] demonstrated that the addition of iron stimulated the growth of toxigenic *Pseudo-nitzschia* spp., providing a competitive advantage over other phytoplankton. Each of these hypotheses requires further validation.

#### **4. Dysiherbaine and Related Compounds**

#### *4.1. Discovery and Structures*

In 1997, Japanese scientists described a new potent marine excitatory amino acid **74** [70], isolated through homogenization of the sponge *Dyidea herbacea* in water, centrifugation of the extract, and precipitation of high-molecular-weight compounds with 2-propanol. Further purification of water-soluble materials using several types of column chromatography yielded this toxin known as disyherbaine (Figure 5). Its structure was identified as a novel diamino dicarboxylic acid using NMR, FABMS, ISIMS, and other methods of molecular structure analysis. Structurally, the acid contains the bicyclic core consisting of *cis*-fused tetrahydropyran and tetrahydrofuran rings with a glutamic acid fragment attached to the tetrahydrofuran moiety. Dysiherbaine core contains four contiguous stereogenic centers with an additional quaternary stereocenter in the tetrahydrofuran moiety at the site of amino acid section attachment. This excitatory acid stimulates binding of kainic acid and 1-amino-3-hydroxy-5-methyl-4-isooxazolepropionic acid, but not *N*-methyl-D-aspartic acid to the rat brain synaptic membranes, suggesting that **74** is an agonist of KARs in CNS.

Radioligand binding assay showed that dysiherbaine binds kainic acid receptors at significantly lesser concentrations than other agonists of KARs. Intraperitoneal injection into mice (20 μg/kg) caused the same behavior as that observed after injection of domoic acid. In general, dysiherbaine exhibits the most potent epileptogenic activity among so far known amino acids. ED50 for substitution of kainic acid, labeled by tritium in kainate receptors by dysiherbaine is 0.00074 μM. This excitatory amino acid is useful for evaluating the physiological roles of KARs in the central nervous system [71].

The above-mentioned findings explained the increased attention to synthesis **74** and related compounds. Another excitatory amino acid, neodysiherbaine A **75** (Figure 5), was isolated by a bioassay-guided chromatographic procedure as a minor constituent of the aqueous extract from the same sponge species. Its structure was deduced by NMR and MS methods and unambiguously confirmed by the total synthesis. After HPLC purification, Japanese scientists obtained as small amount of **75** as 0.26 mg [72]. Neodysiherbaine A is also potent agonist of KARs which induces characteristic epilepsy-like seizures in mice. Like dysiherbaine, it activates neuronal glutamate receptors with a considerable preference toward kainic acid receptors. However, neodysiherbaine is less active in comparison with dysiherbaine: the same activity associated with crowding out kainic acid from kainate receptors is induced by 0.052 μM of neodysiherbaine [72].

**Figure 5.** Structures of dysiherbaine (**74**) and neodysiherbaine (**75**).

After the discovery of dysiherbaine, it was established that various fragments of its structure play different roles in interaction with receptors. The glutamate section of this molecule is responsible for binding to a receptor, while structural and stereochemical features in the tetrahydropyran ring determine the profile of its activity, in particular, agonistic or antagonistic properties [70,71].


**5. Methodology**

This study is the first to empirically test the relationship-based approach of rural destination brand development, and the consideration for the inclusion of multiple stakeholders' voices in terms of how they see themselves in connection to the development of the tourism destination brand. Therefore, the research paradigm is structured around interpretivism [64]; the method is qualitative in nature [65]; and reflective account of 'the researchers in the tourism research' ([66], p. 260).

#### **5.1 The context**

Bario a rural tourism destination in Sarawak (Borneo) in Malaysia has been preselected from an extensive panel of researchers at the national level following a long-term research grant scheme (LRGS) of RM9 million (or US\$3 million as of 2011) from the Ministry of Education Malaysia. Bario is one of the 10 rural destinations in the list ([67], p.8). The choice of Bario over other pre-selected rural destinations is because of its unique remote destination. Bario is not easily accessible; the means of transportation is limited to tourists compared to other rural tourism destinations in Malaysia with similar offerings such as Taman Negara, Royal Belum Park and Kota Kinabalu Park which are easily accessible to tourists by roads [68].

#### **5.2 The pilot study**

The primary data collection method for this study was the in-depth interview method; this was supplemented by participant observation and documentary evidence. A pilot study was first conducted in July 2013 by the first author with ten participants. This is consistent with Ghauri and Gronhaug [69], and Yin [70] that a pilot study or pretesting is a good approach of preparing the actual data collection, before refining the interview questions.

#### **5.3 Participants**

The participants were chosen based on the relationship-based approach to comprise of all levels and categories of stakeholders. For the study criteria as participants, the following procedures were followed. A total number of 55 participants were approached for this study and 48 were included for analysis. These participants included the tourists who were in Bario, specifically the selection criteria of having spent a considerable amount of time engaging with Bario community. All participants were informed with a request letter for participation in advance before the actual interviews were conducted. A semi-structured interview protocol was developed that focuses on the main question: 'How can a destination brand framework for rural tourism be developed using the relationship-based approach? To provide answers to the main research question, this study provides the following specific research questions: (a) What are the tourism destinations' appeals in developing a destination brand for rural tourism? (b) What are the destinations' branding strategies involved in destination brand building for rural tourism? And

*Developing a Rural Tourism Destination Brand Framework from the Perspective… DOI: http://dx.doi.org/10.5772/intechopen.93839*

(c) what are the roles of tourism destination stakeholders in developing a destination brand for rural tourism?

The in-depth interviews were conducted in five different locations namely, Bario, Miri, Kuching, Shah Alam and Putra Jaya: Prime Minister's Department - Performance Management and Delivery Unit (PEMANDU) in Malaysia from April to September 2014. The in-depth interview sessions lasted an average of 60 minutes and were digitally recorded [71]. Transcription was undertaken immediately after the conclusion of the interview [72], so that the data collected from the participants would still be fresh in the researcher's mind [73]. In addition to the in-depth interviews, participant observation was carried out in Bario for a total of 30 days. As a result, 50 pages of field notes were generated as a narrative account to record all the events, places visited and activities in Bario. In order to enhance the validity and reliability of participant observation, this study adopted the seven steps suggested for participant observation by Cresswell [74], pp.134-135. This study also followed the recommendation of Tilstone [75] that the participant observation should address the context (i.e. date, time, length of observation, and activities or events) and content (i.e. stakeholders' involvement in local events) of the phenomenon being studied. In addition, documentary evidence such as brochures and printed materials in relation to Bario were also used to complement the data obtained from both in-depth interviews and participant observation. Scott [76]'s four criteria for assessing the quality of documentary evidence (authenticity, credibility, representativeness and meaning) were used as a guide to assure validity and reliability of the collected materials.

#### **5.4 Data analysis**

destination success within the Mournes, Northern Ireland [35]. Based on the different explanations from literature sources presented in this section, the methodology section reveals research approach, data collection methods and analytic techniques

This study is the first to empirically test the relationship-based approach of rural destination brand development, and the consideration for the inclusion of multiple stakeholders' voices in terms of how they see themselves in connection to the development of the tourism destination brand. Therefore, the research paradigm is structured around interpretivism [64]; the method is qualitative in nature [65]; and reflective account of 'the researchers in the tourism research' ([66], p. 260).

Bario a rural tourism destination in Sarawak (Borneo) in Malaysia has been preselected from an extensive panel of researchers at the national level following a long-term research grant scheme (LRGS) of RM9 million (or US\$3 million as of 2011) from the Ministry of Education Malaysia. Bario is one of the 10 rural destinations in the list ([67], p.8). The choice of Bario over other pre-selected rural destinations is because of its unique remote destination. Bario is not easily accessible; the means of transportation is limited to tourists compared to other rural tourism destinations in Malaysia with similar offerings such as Taman Negara, Royal Belum Park and Kota Kinabalu Park which are easily accessible to tourists by roads [68].

The primary data collection method for this study was the in-depth interview method; this was supplemented by participant observation and documentary evidence. A pilot study was first conducted in July 2013 by the first author with ten participants. This is consistent with Ghauri and Gronhaug [69], and Yin [70] that a pilot study or pretesting is a good approach of preparing the actual data collection,

The participants were chosen based on the relationship-based approach to comprise of all levels and categories of stakeholders. For the study criteria as participants, the following procedures were followed. A total number of 55 participants were approached for this study and 48 were included for analysis. These participants included the tourists who were in Bario, specifically the selection criteria of having spent a considerable amount of time engaging with Bario community. All participants were informed with a request letter for participation in advance before the actual interviews were conducted. A semi-structured interview protocol was developed that focuses on the main question: 'How can a destination brand framework for rural tourism be developed using the relationship-based approach? To provide answers to the main research question, this study provides the following specific research questions: (a) What are the tourism destinations' appeals in developing a destination brand for rural tourism? (b) What are the destinations' branding strategies involved in destination brand building for rural tourism? And

adopted in this study.

*Tourism*

**5. Methodology**

**5.1 The context**

**5.2 The pilot study**

**5.3 Participants**

**282**

before refining the interview questions.

Thematic analysis was adopted to analyse the data collected from the in-depth interviews.  The themes emerged from the study's findings. This study also used the six stages of thematic analysis as recommended by Braun and Clarke [78] which sees the researcher: (1) familiarising with the data; (2) developing the initial codes (or open codes); (3) searching for the relevant themes; (4) reviewing themes that have emerged; (5) defining, labelling or naming the codes; and (6) producing a report of the findings. This analytic method specifically identified codes and themes that provide answers to the main questions. Finally, content analysis was used to analyse the field notes from the participant observation and documentary evidence as supplementary data to the in-depth interviews. Content analysis is widely used in tourism research [79].

#### **6. Findings and discussion**

This section presents the findings based on the triangulation of data sources (indepth interviews, participant observation and documentary evidence) used in this study. The case study presents an in-depth investigation into Bario as a unique study context of a rural tourist destination in Malaysia. The main aim of this study is to develop a destination brand framework for rural tourism destinations using the relationship-based approach. The number of participants is presented in **Table 3** and the main findings from the research questions are presented in three sections. For the purpose of anonymity, participant code number (PCN) representing identification of each of the participant were used.

*Source: Developed for this study.*

*Legend: STB, Sarawak Tourism Board; DoI – Department of Immigration; MOT – Ministry of Tourism. MTTF, Miri Tourism Task Force; PEMANDU- Performance Management and Delivery Unit.*

#### **Table 3.**

*Participants' profile.*

The 48 participants interviewed came from eight different countries or five continents of (Europe, North America, Asia, Oceania (Australia and New Zealand), and Africa) as shown in **Table 3** and they are in the age range of 20 to 68. The number of days spent by these tourists was important because their experiences would have been enriched to provide relevant responses to the in-depth interview questions. This view is consistent with Prayag and Ryan [73] that this was important in order to capture the essence of the place and "where visitors' experiences were complete". The following section presents findings on research question one.

*… If you have been to Bario it is remote; the jungle is also unique - that would be another area where people would also be interested to go and visit … the food … for example, is Bario rice is a form of highland specie you don't see … anywhere else in*

conference

Communal relationship with people

b. Educated community

Hard factors Historical and archaeological sites – megaliths and stone monuments

b. Sense of belonging

b. World challenge organisation c. "Bario Revival" book Destination accessibility Accessibility by smaller aircraft and logging road on 4WD

viewed as adventure tourism and unique

a. Name changing ceremony (IRAU in Kelabit)

b. Annual Bario revival anniversary and conference

a. eBario knowledge fair or developmental

b. Traditional wedding ceremony

Destination image a. Traditional longhouses as tourist product

*Developing a Rural Tourism Destination Brand Framework from the Perspective…*

Destination awareness and identity a. Food festival and cultural events

Soft factors a. Relationship building experience

The image of Bario seems to be of a unique destination due to its location, nature, traditional farming and food attractions. The positive perception of a rural tourism destination is important in order to draw the attention of would**-**be visitors. This view is shared by Anholt [80] that destination image is very crucial for the travel and tourism industry, and this accounts for the rationale why great importance has been attached to destination branding. The participants' views on destination image are consistent with the literature on the attributes that determine the perceived destination image such as trekking, scenery, weather condition, hotel and self-catering accommodation, relaxation and gastronomy [12]. In Bario, there is no hotel facility but alternatively, there are traditional Bario (Kelabit) longhouses where visitors could stay with multiple family members. These longhouses are unique to rural destinations; more specifically, these longhouses are found in very few rural tourism destinations and Bario prides itself with significant numbers of longhouses. This traditional system of accommodation is a niche product in Bario's tourism and hospitality services. By living in the longhouses, it provides the visitors an opportunity to learn quickly about the culture and lifestyle of the host. This is

This section addresses research question two. The aim was to identify the desti-

nation branding strategies in developing a destination brand for rural tourism.

*the country.(PCN38).*

**Main themes Findings**

*DOI: http://dx.doi.org/10.5772/intechopen.93839*

Characteristics of rural tourism

Community-based tourism and Cultural events (CBTCEs)

and exhibitions (L-MICE)

*Tourism destination appeals.*

*Source: Authors.*

**Table 4.**

**285**

Local meetings, incentives, conventions

destinations

followed by findings from research question two.

**8. Rural destination branding strategies**

### **7. Tourism destination appeals**

Thus far, this section has reported findings that seek to answer the first research question that reads: 'What are the destination appeals in developing a destination brand for rural tourism?' The objective was to identify tourism destination attractions. Findings indicate there are eight rural tourism destination appeals as presented in **Table 4**. These constructs contribute to the existing literature on the tourism destination appeals which are conceptualised in developing a destination brand framework for rural tourism using the relationship-based approach.

The following are the extracts from the participants' opinions on the tourism destination appeals. When asked if Bario is a rural tourism destination, comments from respondents illustrating this point include a statement from a key informant from the Ministry of Tourism in Sarawak:

*Basically, if you look at the image of Bario, the geographic location itself is already rural. … in Bario most people will agree that it is still rural because you have difficulty in getting there, you stay in old Kelabit longhouses, there is no road and you don't have 24 hours of electricity supply and water supply; so the characteristics of Bario itself is already rural. (PCN34).*

Moreover, a director from PEMANDU in the Prime Minister's Department in Malaysia echoed:

**Main themes Findings** Characteristics of rural tourism destinations Communal relationship with people Destination image a. Traditional longhouses as tourist product b. Educated community Destination awareness and identity a. Food festival and cultural events b. World challenge organisation c. "Bario Revival" book Destination accessibility Accessibility by smaller aircraft and logging road on 4WD viewed as adventure tourism and unique Hard factors Historical and archaeological sites – megaliths and stone monuments Soft factors a. Relationship building experience b. Sense of belonging Community-based tourism and Cultural events (CBTCEs) a. Name changing ceremony (IRAU in Kelabit) b. Traditional wedding ceremony Local meetings, incentives, conventions and exhibitions (L-MICE) a. eBario knowledge fair or developmental conference b. Annual Bario revival anniversary and conference *Source: Authors.*

*Developing a Rural Tourism Destination Brand Framework from the Perspective… DOI: http://dx.doi.org/10.5772/intechopen.93839*

#### **Table 4.**

The 48 participants interviewed came from eight different countries or five continents of (Europe, North America, Asia, Oceania (Australia and New Zealand), and Africa) as shown in **Table 3** and they are in the age range of 20 to 68. The number of days spent by these tourists was important because their experiences would have been enriched to provide relevant responses to the in-depth interview questions. This view is consistent with Prayag and Ryan [73] that this was important in order to capture the essence of the place and "where visitors' experiences were complete". The following section presents findings on research question one.

*Legend: STB, Sarawak Tourism Board; DoI – Department of Immigration; MOT – Ministry of Tourism. MTTF, Miri*

*Tourism Task Force; PEMANDU- Performance Management and Delivery Unit.*

**Participants No. of participants**

Local residents, Kelabits in diaspora and tourism entrepreneurs in Bario 17 Local tourist 1 International tourists 14 Government agencies – STB, PEMANDU, DoI, MOT, & MTTF 6 Non-government organisations (NGOs) and volunteers 5 Branding and marketing experts 2 Academic researcher 1 Airline Company (sole rural air services provider to Bario) 1 Mechanised rice farming investor in Bario 1 Total number of participants 48

Thus far, this section has reported findings that seek to answer the first research question that reads: 'What are the destination appeals in developing a destination brand for rural tourism?' The objective was to identify tourism destination attractions. Findings indicate there are eight rural tourism destination appeals as presented in **Table 4**. These constructs contribute to the existing literature on the tourism destination appeals which are conceptualised in developing a destination brand framework for rural tourism using the relationship-based approach.

The following are the extracts from the participants' opinions on the tourism destination appeals. When asked if Bario is a rural tourism destination, comments from respondents illustrating this point include a statement from a key informant

*Basically, if you look at the image of Bario, the geographic location itself is already rural. … in Bario most people will agree that it is still rural because you have difficulty in getting there, you stay in old Kelabit longhouses, there is no road and you don't have 24 hours of electricity supply and water supply; so the characteristics*

Moreover, a director from PEMANDU in the Prime Minister's Department in

**7. Tourism destination appeals**

*Source: Developed for this study.*

**Table 3.**

*Tourism*

*Participants' profile.*

from the Ministry of Tourism in Sarawak:

*of Bario itself is already rural. (PCN34).*

Malaysia echoed:

**284**

*Tourism destination appeals.*

*… If you have been to Bario it is remote; the jungle is also unique - that would be another area where people would also be interested to go and visit … the food … for example, is Bario rice is a form of highland specie you don't see … anywhere else in the country.(PCN38).*

The image of Bario seems to be of a unique destination due to its location, nature, traditional farming and food attractions. The positive perception of a rural tourism destination is important in order to draw the attention of would**-**be visitors. This view is shared by Anholt [80] that destination image is very crucial for the travel and tourism industry, and this accounts for the rationale why great importance has been attached to destination branding. The participants' views on destination image are consistent with the literature on the attributes that determine the perceived destination image such as trekking, scenery, weather condition, hotel and self-catering accommodation, relaxation and gastronomy [12]. In Bario, there is no hotel facility but alternatively, there are traditional Bario (Kelabit) longhouses where visitors could stay with multiple family members. These longhouses are unique to rural destinations; more specifically, these longhouses are found in very few rural tourism destinations and Bario prides itself with significant numbers of longhouses. This traditional system of accommodation is a niche product in Bario's tourism and hospitality services. By living in the longhouses, it provides the visitors an opportunity to learn quickly about the culture and lifestyle of the host. This is followed by findings from research question two.

#### **8. Rural destination branding strategies**

This section addresses research question two. The aim was to identify the destination branding strategies in developing a destination brand for rural tourism.

Findings show that there are eleven destination branding strategies for rural tourism destinations uncovered with the potential contributions in developing a destination branding framework as shown in **Table 5**.

development of a destination logo and tagline because they remind the visitors about the destination. These findings are in line with the existing literature on destination branding strategies and critical success factors (CSFs) of developing a destination brand [34, 80]. Furthermore, a tourist from Austria commented:

*Developing a Rural Tourism Destination Brand Framework from the Perspective…*

*I think it would also be good to have brochures about Bario to take along and show people all over the place is a beautiful place to visit, the attractions, the culture, megaliths, the paddy rice fields, the hospitable people in Bario, homestay, the longhouses, everything must be featured in the brochure something they can hold that*

Brochures have been used in many destinations to promote tourism [81]. In the case of Bario brochures have not been used to really promote tourism and develop its destination brand. It is also being suggested that the heart of Borneo and East Asia Growth area (EAGA) strategy should be used. This is because EAGA is an international collaboration of four countries namely Brunei, Indonesia, Malaysia and Philippines (BIMP). Findings also indicate that Bario should be developed gradually and not overdeveloped in order to maintain its basic characteristics and preserve the tourist attractions. The establishment of a tourist and visitors information centre (TVIC) is suggested so that it would be a one stop centre where the visitors would have information on different tourism activities available and where to visit. Importantly, findings from research question three is presented in the following section.

This section addresses research question three. This study has uncovered eight constructs and potential contributions to tourism destination stakeholders' roles. These contributions to the existing literature on the destination stakeholders' roles are conceptualised in developing a destination brand framework for rural tourism

Findings in this study also support extant literature on the issue of leadership in tourism destination which has always been an interesting subject and viewed by researchers and practitioners alike across different disciplines as very complex. The participants'statements in relation to the sources of community leadership initiative in relationship building are presented in the following sections. According to a local

*I think in Bario there are one or two community associations so they could appoint representatives or leaders among them who will be saddled with the responsibility of*

Comments from other participants on who should spearhead the responsibility and become a bridge builder [82] among the stakeholders include that of a tourist

*I think the local community should initiate it [leadership] if they want Bario to be branded through the local leaders in collaboration with other stakeholders …*

Findings show that the leadership initiative to promote relationship building should be initiated from the local community because the local people know more about their community and how they want tourism to be promoted in Bario. In the

*is tangible to take along. (PCN32).*

*DOI: http://dx.doi.org/10.5772/intechopen.93839*

**9. Tourism destination stakeholders' roles**

resident, retiree and farmer in Bario said:

from Germany:

**287**

*(PCN20).*

using the relationship-based approach as presented in **Table 6**.

*meeting with other stakeholders in Bario. (PCN4).*

Extracts from the participants' opinions on the destination branding strategies include that of a tourist from the United States of America:

*It has to start with the relationship building among the … Bario people … they should work with the local authority and the state to promote … and ensure that the destination image of Bario and its attractions are well communicated … (PCN24).*

The destination branding strategies of tourism destinations are diverse and come from different segments of the tourism destination. Findings show that relationship building, local community involvement and communication of the brand are key success factors mentioned by the participants. Other strategies include the

*Developing a Rural Tourism Destination Brand Framework from the Perspective… DOI: http://dx.doi.org/10.5772/intechopen.93839*

development of a destination logo and tagline because they remind the visitors about the destination. These findings are in line with the existing literature on destination branding strategies and critical success factors (CSFs) of developing a destination brand [34, 80]. Furthermore, a tourist from Austria commented:

*I think it would also be good to have brochures about Bario to take along and show people all over the place is a beautiful place to visit, the attractions, the culture, megaliths, the paddy rice fields, the hospitable people in Bario, homestay, the longhouses, everything must be featured in the brochure something they can hold that is tangible to take along. (PCN32).*

Brochures have been used in many destinations to promote tourism [81]. In the case of Bario brochures have not been used to really promote tourism and develop its destination brand. It is also being suggested that the heart of Borneo and East Asia Growth area (EAGA) strategy should be used. This is because EAGA is an international collaboration of four countries namely Brunei, Indonesia, Malaysia and Philippines (BIMP). Findings also indicate that Bario should be developed gradually and not overdeveloped in order to maintain its basic characteristics and preserve the tourist attractions. The establishment of a tourist and visitors information centre (TVIC) is suggested so that it would be a one stop centre where the visitors would have information on different tourism activities available and where to visit. Importantly, findings from research question three is presented in the following section.