Distributed Computations in Real Time Based on a Rough Grammar Principle

Abstract

A novel methodology for high performance computing in real time is presented basedo a rough grammar approach. Using the rough grammar we sequence dynamically all the tasks in a processor net in a pipeline fashion. The duration of each pipeline stage is normalized to the duration of one of the shorter tasks, by which a reduction of the idle and wait times of nodes to a minimum is achieved. The simulationsshow that the node busyness is almost one hundred percent at each node for an arbritrary algorithm and without knowing the task execution times in advance. Higher linear improvement is achieved by allocating the next nodes for a smaller quantum (e.g., at 10% of tasks completed) and passing all the tasks forward when the quantum expires.