Skip to end of metadata
Go to start of metadata

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 10 Next »

Project Overview

Responsible:

Related Theses:

  • not finished yet

WARNING: THIS PAGE IS CURRENTLY UNDER CONSTRUCTION. THE CONTENT MIGHT CHANGE EVERY FEW MINUTES!

The Priority-Based Compilation

The priority-based low-level compilation approach uses the established compiling chain for SCCharts until the dependency analysis of the SCG is finished. From this point, either the netlist low-level compilation approach or the priority-based low-level compilation approach can be used. Because of the different approaches, it is possible, that one of the compiler finds a valid schedule for an SCChart, while the other fails.

 

General

The priority-based low-level compilation approach compiles an SCG enriched by the results of the dependency analysis to SCL_P, whose basis is the programming language C and which is enriched by the SCL_P macros. Therefore the regions of the SCG are fragmented into threads, whose priority determines the order in which the threads are executed. A thread might change its priority, which results in a context switch. The adiministration of the threads is done by the SCL_P macros. As the calculation of the thread priorities is not trivial, it done stepwise, which should help the user to understand how it is done. This is provided by a KiCo compilation chain, which can be called from the SCCharts editor or from the SCG editor.The image below shows the compilation chain as shown by the SCChart editor:

 

 

The target language SCL_P:

SCL_P is a leaner variant of Synchronous C. It also provides a deterministic thread administration for C which is implemented as macros. As the grammar of an SCG is simpler, less macros are required than for Synchronous C. The macros provided to a programmer are shown below.

Each thread is identified by a unique prioID, which acts as identifier and as priority for the scheduling. The prioID can be changed, e.g. if a thread waits for a result from another thread. The threads are scheduled in descending order of their corresponding prioID. SCL_P uses cooperative scheduling.

 

Macros 
tickstart(p)
Starts the program, the main thread gets the priority p
forkn(label1, p1, ...,  labeln, pn)
Forks n processes, which start at label labeln and have priority pn
par
Acts as barrier between two threads, deactivates the thread before the barrier and removes it
joinn(p1, ...)
Waits until all prioIDs between the braces have finished. It is necessary to consider every prioID, which a thread might have during its execution.
prio(p)
Changes the prioID of the current thread, which usually results in a context switch
pause
pauses the current thread, as a result, the next thread is started
tickreturn()
Returns if program has finished

 

Requirements for a translation to SCL_P:

  • Each thread needs at least one unique prioID.
  • The first child inherits the prioID of the parent thread
  • The parent threads inherits the prioID of the thread, which performs the join afterwards.
  • The thread whose exit node has the lowest prioID has to perform the join.
  • The thread, which should perform the join is forked last
  • A thread can lower it's prioID during a tick, it should only rise its prioIDs just before a pause.

Transformation Steps

The expected input for the compilation chain is an SCG enriched by the results of the depenency analysis. As the compiler does not use any other results from previous compilation steps, any transformation chain, which results in an SCG can be used.The stepwise calculation of the node priorities and the code generation are described in this section.

Requirements for a translation to SCL_P:

  • Each thread alway needs to have a unique priority, because the priority is used as a priority for the schedule and additionally, the priority is used as identifier for the thread. Therefore the resulting priority for the schedule is called prioID
  • The thread, which is forked first should have the highest prioID, because SCL_P only provides cooperate scheduling and the first thread ist started first (in this case the first thread alsway has the same prioID its the parent thread - because of the calculation below)
  • The parent threads inherits the prioID of the thread, which performs the join
  • The thread whose exit node has the lowest prioID has to perform the join.
  • The thread, which should perform the join is forked last
  • A thread can lower it's prioID during a tick, it should only rise its prioIDs just before a pause.

OptimizeSCG:

The OptimizeSCG transformation deletes regions from the SCG, which only consist of an enty and exit node. After the code generation, these regions are transformed to empty threads, which only consist of a label and are therefore rejected by a later compilation of the resulting SCL_P/C program. However, for real world examples, it is unlikely, that the user models a region without any further functionalty, therefore this step might be removed.

NodePriorities:

This transformation step uses the results from the dependency analysis. It checks, whether a valid schedule for the SCG exists and calculates the node priorities afterwards. Therefore, the strongly connected components of the SCG are calculated, where the nodes of the SCG are the nodes of directed the graph which is connected by dependency and transition edges. Pause edges are ignored. If such a strongly connected component contains a dependency edge, the SCG is not schedulable. Otherwise, the SCG is schedulale and the node priorities, which are crucial for the schedule, can be determined. The priority of a node is the longest path originating from that node, where strongly connected components are considered as a single node and transition edges have weight 0  and dependency edges have weight 1. Again, pause edges are ignored. The theoretical foundation of this transformation step can be found here.

OptNodePriorities:

This transformation step is optional. It reduces the number of context switches. Surface nodes usually have the priority 0. Additionally, exit nodes usually have the same priority as the exit nodes of their sibling threads. However it is often unnecessary to perform a context switch, just because an exit or surface node appears, especially because in this case, the order in which the exit/surface nodes are scheduled does not matter. Therefore the exit and surface nodes are taken as starting point. The algorithm moves upward from those nodes and checks, whether any parent node with a higher priority exists. If more than one parent exists, the minimal priority is taken. The search terminates immediatly, if an entry, join or depth node is found and additionally, if a node has an incoming dependency. This is important, because otherwise, the order of the threads might be corrupted.

ThreadSegmentIDs:

SCL_P requires unique priorities for the schedule. In case, that nodes of different threads have the same priority, the thread segment IDs decide, which thread comes first. As described above, a thread, which forks other threads hands it's own prioID, and therefore it's thread segment ID over to the first child and inherits the prioID and therefore the thread segment ID from the child, which performs the join. The assignment of the thread segment IDs is done by a modified depth-first search, which stops at each join node, until its predecessors have received their thread segment ID. Because a prioID should be only lowered, the assignment algorithm starts with the highest thread segment ID, which is calculated by (number of entry nodes) - (number of forknodes). Although the thread segment ids are shown within the region, additionally the unoptimized prioIDs are shown within the graph. This is because a thread segment ID changes after a join and it should help the user to understand, which node belongs to which thread segment ID.

OptPrioIDs:

The unique prioIDs are calculated by the following formula:

prioID = (node priority) * (number of thread segment ids) + (thread segment id)

The drawback of this formula is, that many prioIDs remain unused. This transformation compresses the prioIDs in use. If any prioID is unused, the thread with the next higher prioID gets that prioID. This makes the bookkeeping for SCL_P more compact.

 

Packages belonging to this Project:

 

de.cau.cs.kieler.scg.prios: - Enthält die Prioritätenberechnung, und die ist ja der spannendste Teil 

de.cau.cs.kieler.scg.prios.sclp - Enthält die Übersetzung vom SCG nach Scl_P - Vielleicht noch etwas chaotisch, wir wollten ja auch nochmal über die Makros reden...
de.cau.cs.kieler.kexpressions.c - Enthält die Übersetzung der KExpressions nach C (wird für die Übersetzung nach Scl_P benötigt)
de.cau.cs.kieler.sclp - Eine modifizierte Kopie von de.cau.cs.kieler.sc, angepasst für Scl_P (wird für die Simulation benötigt) - Hier liegen die Makros... die sind auch noch nicht aufgeräumt, aber immerhin funktionsfähig de.cau.cs.kieler.sccharts.sim.sclp - Eine modifizierte Kopie von de.cau.cs.kieler.sccharts.sim.c für die Simulation
de.cau.cs.kieler.sccharts.sim.sclp.test - Eine modifizierte Kopie von de.cau.cs.kieler.sccharts.sim.c.test
Weitere Änderungen an bestehenden Dateien: de.cau.cs.kieler.scg.klighd: SCGraphDiagramSynthesis.xtend - Einblenden der Prioritäten

 

 

 

 

  • No labels