## 2 System Model
### Optimization: Scheduling Computation Acceleration Algorithm
GCL Output: Once all streams that can be successfully placed by this heuristic are scheduled into time slots, their determined start and end slot indices, along with their respective \(PCP_{i}\) values, directly translate into the GCL entries for the TSN switches. It is important to emphasize that as a heuristic method, the proposed acceleration algorithm does not guarantee finding a feasible schedule, even if one exists. Its design prioritizes computational speed over completeness, making it particularly suitable for dynamic environments with limited computational resources for scheduling tasks. In scenarios where the network is highly congested or constraints are extremely tight, the greedy placement and limited backtracking may fail to find a valid GCL. In such cases, the algorithm would report a failure, and a more exhaustive method, such as the SMT-based baseline algorithm, would be required. The primary value of the acceleration algorithm lies in its ability to quickly find high-quality, feasible schedules for the vast majority of practical, non-pathological scenarios. The conceptual pseudo-code for this algorithm is outlined in Algorithm 2. ```
1:Set of schedulable streams/sub-streams \(\mathcal{S}^{\prime}=\{s_{1},\ldots,s_{N}\}\) (output from Algorithm 1, each \(s_{k}\) has attributes like \(id_{k},\text{cycle\_start\_offsets}_{k},\text{duration}_{k},\text{deadline}_{k}, \text{period}_{k},PCP_{k}\)). Hyperperiod \(\mathcal{T}\). Constraints \(\mathcal{C}\) (from Section 2.3). 2:Gate Control List (GCL). 3:Initialize GCL timeline for hyperperiod \(\mathcal{T}\) with all 1 us slots marked as AVAILABLE. 4:Sort \(\mathcal{S}^{\prime}\) using the two-level sorting strategy: (1) by earliest cycle start time instance in \(\mathcal{T}\), then (2) by stream duration (ascending). 5:Let \(\text{{PlacedInstances}}\leftarrow\emptyset\). \(\triangleright\) A set to track successfully placed stream instances
6:for all\(s_{k}\in\mathcal{S}^{\prime}\) (in sorted order) do
7:for all cycle instance \(\mu\) of \(s_{k}\) within \(\mathcal{T}\)do
8:\(\textit{is\_placed\_this\_instance}\leftarrow\textit{false}\). 9: Determine earliest valid start slot \(slot_{start}\) for \(s_{k}\) in instance \(\mu\). 10:\(\textit{current\_attempt\_slot}\leftarrow\textit{slots}_{start}\). 11:while\(\textit{current\_attempt\_slot}+\text{duration}_{k}\leq\text{deadline\_for\_instance}_{\mu}(s_{k})\)and not is\(\textit{\_placed\_this\_instance}\)do
12:if Slots from \(\textit{current\_attempt\_slot}\) to \(\textit{current\_attempt\_slot}+\text{duration}_{k}-1\) are AVAILABLE and placement satisfies \(\mathcal{C}\)then
13: Mark slots as OCCUPIED by instance \((s_{k},\mu)\) in GCL timeline. Add \((s_{k},\mu)\) to \(\text{{PlacedInstances}}\). 14:\(\textit{is\_placed\_this\_instance}\leftarrow\textit{true}\). 15:else
16:\(\textit{current\_attempt\_slot}\leftarrow\textit{current\_attempt\_slot}+1\). \(\triangleright\) Try next us slot
17:if not is\(\textit{\_placed\_this\_instance}\)then
18:\(\textit{ConflectingInstances}\leftarrow\text{Identify instances in }\text{{PlacedInstances}}\) that occupy desired slots for \((s_{k},\mu)\). 19: Sort \(\textit{ConflectingInstances}\) by priority (ascending, i.e., lower PCP first). 20:for all instance \(s_{\textit{conflict}}\) in \(\textit{ConflectingInstances}\)do
21: Temporarily remove \(s_{\textit{conflict}}\) from GCL timeline and \(\text{{PlacedInstances}}\). 22:if can place \((s_{k},\mu)\) in the now-available slot then
23: Place \((s_{k},\mu)\) in GCL timeline. Add \((s_{k},\mu)\) to \(\text{{PlacedInstances}}\). 24:if can find a new valid slot for \(s_{\textit{conflict}}\)then
25: Place \(s_{\textit{conflict}}\) in its new slot. Add \(s_{\textit{conflict}}\) back to \(\text{{PlacedInstances}}\). 26:\(\textit{is\_placed\_this\_instance}\leftarrow\textit{true}\). 27:break\(\triangleright\) Conflict resolved, exit inner For loop
28:else
29: Revert: Place \(s_{\textit{conflict}}\) back, remove \((s_{k},\mu)\) from GCL timeline and \(\text{{PlacedInstances}}\).