Abstract
In this paper, a new methodology for tolerating link as well as node defects in self-adaptive reconfigurable networks will be presented. Currently, networked embedded systems need a certain level of redundancy for each node and link in order to tolerate defects and failures in a network. Due to monetary constraints as well as space and power limitations, the replication of each node and link is not an option in most embedded systems. Therefore, we will present a hardware/software partitioning algorithm for reconfigurable networks that optimizes the task binding onto resources at runtime such that node/link defects can be handled and data traffic on links between computational nodes will be minimized. This paper presents a new hardware/software partitioning algorithm, an experimental evaluation and for demonstrating the applicability, an implementation on a network of FPGA-based boards.
Problem Statement: Static Binding and Network Fragility
In traditional networked embedded systems, such as those found in automotive architectures, functions are statically bound to specific Electronic Control Units (ECUs). This static configuration creates a single point of failure: if a node or communication link fails, the associated functionality is lost unless expensive, redundant hardware is pre-installed.
While reconfigurable devices like FPGAs offer the potential to move tasks between nodes at runtime, existing load-balancing algorithms often fall short by ignoring three critical factors:
- Heterogeneity: Sensors and actuators are physically tied to specific nodes, restricting where certain tasks can reside.
- Communication Costs: Migrating a task to balance CPU load might inadvertently saturate network links with increased data traffic.
- Hardware/Software Partitioning: Tasks can be implemented as either software (CPU) or hardware (FPGA logic), each with distinct resource footprints.
Proposed Methodology: A Two-Phase Self-Healing Approach
The authors propose a decentralized, two-phase methodology to achieve "self-healing" without massive hardware over-provisioning.
1. Fast Repair Phase
Upon detecting a node or link failure, the system immediately switches to pre-placed "replica" tasks on healthy nodes. This phase prioritizes speed, restoring basic functionality within milliseconds (approximately 0.89ms per hop in prototypes), even if the resulting task placement is sub-optimal.
2. Optimization Phase
Following the initial repair, a distributed hill-climbing algorithm reorganizes task bindings. To prevent routing instability, a token-passing mechanism ensures only one node migrates a task at a time. The optimization is guided by an Improvement Value ($I_{i,j}$) that balances:
- Communication Improvement: Reducing network congestion by moving tasks closer to their data sources or sinks.
- Migration Overhead: Penalizing the movement of large tasks (e.g., FPGA bitstreams) to conserve bandwidth.
- Partitioning Preference: Respecting a task's preference for hardware or software implementation based on performance needs.
Evaluation and Key Results
The approach was validated using synthetic scenarios (up to 200 tasks and 50 nodes) and a physical prototype of four FPGA boards running a driver assistance application.
- Efficiency Gains: The optimization phase reduced total network traffic by at least 20% compared to the post-repair state.
- Resource Utilization: The number of tasks running in their "non-favorite" implementation style was halved, from 50% to 25%.
- Performance: Activating a replica took roughly 4ms, demonstrating the feasibility of the "Fast Repair" for safety-critical embedded contexts.
- Convergence: The distributed approach closely matched the performance of computationally expensive global Evolutionary Algorithms.
Conclusion and Future Directions
By treating the network as a pool of resources rather than fixed boxes, this methodology enables robust fault tolerance. Future work will address the scalability of the token-passing mechanism in very large networks and explore deterministic real-time guarantees during the reconfiguration process.
Summary updated