=Paper=
{{Paper
|id=Vol-1643/paper-03
|storemode=property
|title=Using Reference Attribute Grammar-Controlled Rewriting for Runtime Resource Management
|pdfUrl=https://ceur-ws.org/Vol-1643/paper-03.pdf
|volume=Vol-1643
|authors=Johannes Mey,René Schöne,Daniel Langner,Christoff Bürger
|dblpUrl=https://dblp.org/rec/conf/date/MeySLB16
}}
==Using Reference Attribute Grammar-Controlled Rewriting for Runtime Resource Management==
https://ceur-ws.org/Vol-1643/paper-03.pdf
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
Using Reference Attribute Grammar-Controlled
Rewriting for Runtime Resource Management
Johannes Mey1 , René Schöne1 , Daniel Langner1 , and Christoff Bürger2
1
Chair of Software Technology, TU Dresden, Germany
johannes.mey@tu-dresden.de, rene.schoene@tu-dresden.de,
daniel.langner@mailbox.tu-dresden.de
2
Department of Computer Science, Faculty of Engineering, Lund University, Sweden
christoff.burger@cs.lth.se
Abstract. To make distributed systems resource aware and adaptive,
they can be modeled as self-adaptive systems. Such systems have a view
of their own state and context, which can be represented by a model
that is continuously updated and analyzed at runtime. However, such
analyses need to be concise and efficient to allow large models and high
adaptation rates. To achieve this, we apply reference attribute grammar
controlled rewriting to implement the runtime model of a distributed
task-scheduling case study for energy optimization.
1 Modeling Self-Adaptive Systems
Self-adaptive systems [1] are used to cope with changing requirements and
contextual information at runtime. Furthermore, they need to provide short
response times while maintaining low resource consumption and a convenient
way to specify their internal state and algorithms. Another challenge is the high
update rate of their context information[2]. Self-adaptive systems usually employ
a feedback loop, e.g. MAPE-K [3], and have representation of their context,
e.g. a runtime model. The models@run.time approach [4] uses models not only
during development but also as a data representation at runtime. It has been
shown that auto tuning and resource awareness can save energy in Big Data
scenarios [5]. Our use case is a small, yet scalable, distributed Big Data scenario
on a network of embedded devices. We use a self-adaptive system built around a
runtime model, which is easy to specify, and can run algorithms efficiently with
regard to response time. It employs grammar-based modeling and analysis to
deal with frequent model updates efficiently.
2 Attribute Grammars for Runtime Models
Our solution uses reference attribute grammars [6] (RAGs) as its underlying
technology. RAGs originate from the area of compiler construction to describe
abstract syntax trees of program code. However, their intrinsic advantage –
incremental evaluation – fits well to the described problems. Using RAGs, we
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
describe the structure of runtime models with a context free grammar that is
well-suited for hierarchical structures. Non-hierarchical parts of a model can be
described as well using reference attributes forming arbitrary overlay graphs. The
analysis of runtime data is done using attributes, which are defined declaratively
for specific non-terminals, achieving a concise specification.
However, the aforementioned updates of the runtime model hinder incremental
evaluation commonly used in RAG systems since they rewrite the AST and
therefore invalidate all previously performed analyses. This work uses a novel
approach called RAG-controlled rewriting (RACR) [7], which treats model changes
as term rewrites [8]. This enables the tracking of dynamic dependencies between
attributes and the model, and thus incremental evaluation across model changes.
Therefore, constantly changing self-adaptive systems can be analyzed efficiently,
thus allowing a more frequent analysis and larger model sizes.
3 Runtime Models with RACR
RACR works in a three-phase process. In the first phase, a context free grammar
with inheritance describing the runtime model is specified, like the one depicted
below for our case study presented in section 4. Terminals are in lowercase and
non-terminals in title case optionally suffixed by an alternative name and a colon.
Root ::= scheduler switching CompositeWorker
AbstractWorker ::= id state timestamp
CompositeWorker : AbstractWorker ::= AbstractWorker *
Switch : CompositeWorker ::=
Worker : AbstractWorker ::= devicetype Queue : Request *
Request ::= id size deadline dispatchtime
The second phase involves the attribution, that is the specification of attributes
for certain non-terminals. Below, the schedule attribute defined for Root is listed.
It reads the terminal scheduler and invokes an attribute to find an insertion
position. All attributes and rewrites are written Scheme, using the API functions
ast-child, create-ast and att-value to get a certain child of a AST node,
create a new AST node and call an attribute, respectively.
( ag-rule schedule
( Root ( lambda ( n time work-id load-size deadline )
( att-value ( ast-child ’ scheduler n ) n
time work-id load-size deadline ))))
At runtime, the system is performing rewrites and attribute evaluations in turns.
Rewrites, like the one shown below, change the model and invalidate cached
attribute values. If those attributes are called, RACR ensures their re-evaluation.
( rewrite-insert
( ast-child ’ Queue worker ) ; l i s t node t o i n s e r t i n t o
index ; position of insertion
( create-ast ’ Request ( list id size deadline #f )))
; s u b t r e e f o r t h e new r e q u e s t
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
1. reads Request
2. calls
schedule
Root id: Request4
scheduler: l.c.s schedule-shortest-queue size: 100.00
switching: 1-3 schedule-load-consolidating deadline: 11:11:00
new request
Switch
id: Switch1 find-insertion-pos
rewrite-insert
state: RUNNING
Worker workload-heuristic
workload-heuristic
Worker
Worker workload-heuristic Root
id: Cubie3 find-insertion-pos
find-insertion-pos
id:
id: Cubie3
Cubie3 find-insertion-pos
state: RUNNING
state:
state: RUNNING
RUNNING Switch
Request
Request
Request
id:
id: Request1 Worker
Worker
id: Request1
Request3 Worker
size:
size: 123.45
size: 123.45
123.45
Switch deadline: 12:00:00 Request
deadline:
deadline: 12:00:00
12:00:00 Request
Request
id: Switch1 Request
state: OFF find-insertion-pos
Switch
Worker
Worker workload-heuristic
workload-heuristic
id:
id: Cubie5
Cubie5 find-insertion-pos
Worker
Worker
find-insertion-pos
state:
state: OFF
OFF
original model rewritten model
Fig. 1: Scheduler selection and scheduling of a request. Terminals are contained in
non-terminal boxes, some selected attributes are attached. Terminals not relevant
for the example are left out, l.c.s is the load consolidating scheduler.
4 A Case Study
To investigate the applicability of RACR to self-adaptive systems, we implemented
the distributed indexing of Wikipedia pages using a network of system-on-a-chip
workers [9]. These are Cubieboards having a 1 Ghz CPU, 1GB of RAM, running
Linux, and are connected to a master via switches and Ethernet links. Every
worker and switch is powered by a USB charging hub, which enables the switching
and energy measurement of individual devices.
We developed an adaptation and two scheduling strategies, each written with
RACR. The adaptation strategy controls the number of powered on workers. Our
solution checks periodically for idle workers to be switched off while ensuring
a minimum number of online workers to secure stable performance in case of
load peaks. A round-robin scheduler always chooses the shortest queue, and a
load-consolidating scheduler tries to use as few workers as possible.
The solution is evaluated in a small-scale case study, whose structure and the
scheduling of a request on it are depicted in Figure 1. To analyze our approach’s
scalability, we developed a simulation environment that simulates the execution of
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
Fig. 2: Power consumption when scheduling a workload with a round-robin (top)
and a load-consolidating (bottom) scheduler. The dashed line shows the average
power consumption.
tasks and their associated energy consumption based on models we acquired from
our physical use case. The simulated use case comprises 315 workers connected
via 63 switches fulfilling 4,600 requests within an hour. Figure 2 shows the power
consumption of the two scheduling strategies, using a different color for each
worker. The load-consolidating scheduler (shown at the bottom) uses 6.4% less
energy than the round-robin scheduler while using less workers.
As the model can be modified with rewrites, it permits addition and removal
of workers and the exchange of scheduling and adaptation strategies during
runtime.
5 Conclusion and Outlook
In this work, we showed the applicability of RAG-controlled rewriting for self-
adaptive systems in a distributed data processing use case. In addition, we plan
to conduct more case studies exploring the scalability and adding heterogeneity.
Another case study involves an extended runtime model with included software
structure, in which the presented concepts are applied to iteratively transform
the model to code describing a constraint problem. First measurements show
very short response times for every transformation after the initial one.
Proceedings of 1st Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing (RES4ANT) 2016
In conclusion, RACR enables incremental evaluation for large runtime models
with high update rates, hence offering opportunities for the usage in adaptive,
resource aware systems, such as Big Data systems.
Acknowledgments
This work is partly supported by the German Research Foundation (DFG)
in the SFB 912 “Highly Adaptive Energy-Efficient Computing”, the cluster of
excellence cfaed, and within the Research Training Group “Role-based Software
Infrastructures for continuous-context-sensitive Systems” (GRK 1907).
References
1. R. Lemos et al., “Software Engineering for Self-Adaptive Systems: A Second Re-
search Roadmap,” in Software Engineering for Self-Adaptive Systems II, ser. LNCS,
R. Lemos, H. Giese, H. A. Müller, and M. Shaw, Eds. Springer, 2013, vol. 7475.
2. Y. Chen, J. Dunfield, M. A. Hammer, and U. A. Acar, “Implicit Self-adjusting
Computation for Purely Functional Programs,” in ICFP. New York, NY, USA:
ACM, 2011.
3. J. Kephart and D. Chess, “The vision of autonomic computing,” Computer, vol. 36,
no. 1, Jan. 2003.
4. G. Blair, N. Bencomo, and R. B. France, “Models@run.time,” Computer, vol. 42,
no. 10, Oct. 2009.
5. S. Götz, T. Ilsche, J. Cardoso, J. Spillner, T. Kissinger, U. Aßmann, W. Lehner, W. E.
Nagel, and A. Schill, “Energy-Efficient Databases Using Sweet Spot Frequencies,”
in Proceedings of the 2014 IEEE/ACM 7th International Conference on Utility and
Cloud Computing. IEEE Computer Society, 2014.
6. G. Hedin, “Reference attributed grammars,” Informatica (Slovenia), vol. 24, no. 3,
2000.
7. C. Bürger, “Reference Attribute Grammar Controlled Graph Rewriting: Motivation
& Overview,” in SLE. ACM, 2015.
8. F. Baader and T. Nipkow, Term rewriting and all that. Cambridge university press,
1999.
9. C. Bürger, J. Mey, R. Schöne, S. Karol, and D. Langner, “Using Reference Attribute
Grammar-Controlled Rewriting for Energy Auto-Tuning,” in 10th International
Workshop on Models@run.time, Ottawa, Canada, Sep. 2015.