Mostafa Rizk
email: mostafa.rizk@imt-atlantique.fr

Kevin J M Martin

Jean-Philippe Diguet

J-P Diguet

Run-time remapping algorithm of dataflow actors on NoC-based heterogeneous MPSoCs

Keywords: NoC, Heterogeneous MPSoC, Run-time remapping, Dataflow actor, Move-based algorithm

Multiprocessor system-on-chip (MPSoC) platforms have been emerging as the main solution to cope with processor frequency ceiling and power density issues while still improving performances. Then, network-on-chip (NoC) has been adopted to provide the increasing number of processors with the required communication bandwidth as well as with the necessary flexibility. Video processing and streaming applications are adopting dynamic dataflow model of computation as the need for high performance parallel computing is growing. Dataflow applications executed on modern MPSoC-based architectures are becoming increasingly dynamic and more data-dependent. Different tasks execute concurrently with significant modifications in their workloads and resource demanding over time depending on the input data. Hence, adopting any static or offline dynamic scheduling for mapping tasks will not cope with the computation variations. This paper introduces an original run-time mapping algorithm based on the Move Based (MB) method targeting a dedicated heterogeneous NoC-based MPSoC architecture to achieve workload balancing and optimized communication traffic. The performance of the proposed algorithm is verified by conducting cycle-accurate SystemC simulations of the adopted NoC implementing a real MPEG4-SP decoder. The obtained results reveal the effectiveness of our proposed algorithm. For various real-life videos, the proposed algorithm systematically succeeded to enhance significantly the performance.

I. INTRODUCTION

M ULTIPROCESSOR system-on-chip (MPSoC) plat- forms have been emerging as the main solution to cope with processor frequency ceiling and power density issues while still improving performances. Then, networks-on-chip (NoCs) have been adopted to provide the increasing number of processors with the required communication bandwidth as well as with the necessary flexibility. But legacy code for instance, mainly designed for single or few core architectures, does not scale well with manycore architectures and fails to fully benefit from the available parallelism. However, as discussed decades ago [START_REF] Najjar | Advances in the dataflow computational model[END_REF], dataflow programming can address the limitations of conventional approaches regarding synchronization and shared memory issues. With the rise of massively parallel architectures, we can reconsider the use of dataflow programming as a solution to efficiently exploit the resources of parallel architectures for computing intensive application domains such as video coding, computer vision, machine learning and physics simulation for instance.

A dataflow application can be specified as a graph where nodes, called actors, process data called token(s). The computational models are based on First-In First-Out (FIFO) buffers and respect their formalized read and write rules. Each FIFO holds a set of tokens. Fig. 1(a) illustrates a network of actors, which exchange tokens through defined FIFO channels [START_REF] Martin | Notifying memories: a case-study on data-flow applications with NoC interfaces implementation[END_REF]. Fig. 1(b) presents an example of a structure of the software FIFO generated with the tool ORCC [START_REF] Yviquel | Orcc: Multimedia development made easy[END_REF]. A network of actors holds specific features that make it different from a generic task graph. First, an actor is non-preemptive. Once started, an actor ends its execution. Second, the actor can start if and only if there are enough tokens as input, and enough space in the output FIFOs. The FIFOs are considered updated (i.e. tokens consumed and produced) at the end of the execution of the actor, establishing a conservative synchronization scheme, and preventing from any data race.

When the number of actors is larger than the number of processing elements (PEs), then the main design challenge is the mapping of actors on the network of PEs. In the case of static dataflow [START_REF] Lee | Synchronous data flow[END_REF], where the number of tokens produced and consumed by the actors is known, an optimal solution can be computed offline [START_REF] Lesparre | Evaluation of synchronous dataflow graph mappings onto distributed memory architectures[END_REF]. However, an increasing number of applications cannot be specified with a static graph since the performance improvement of complex applications usually lead to context and data-dependent optimizations. This evolution is, for instance, significant in the domain of video coding. Dynamic models are then used to express data-dependent behavior of some applications [START_REF] Lee | Dataflow process networks[END_REF]. Dynamic dataflow is a useful model of computation (MoC) for handling streaming data and video processing applications.

As the workload of an actor may change according to the input data set, adapting the mapping while the application runs is required to optimize the use of the computing and communication resources. The mapping problem is known as NP-complete. Heuristic methods, for a fast response time, are thus required to address manycore architectures. Runtime adaptation relies on system observation, decisions and configurations. Several previous works have addressed the problem of task mapping at run-time. In [START_REF] Wang | Dynamic application allocation with resource balancing on NoC based many-core embedded systems[END_REF], the authors have proposed a dynamic resource balance algorithm targeting NoC-based Many-core homogenous platforms to enhance the system performance by balancing the utilization of on-chip computing resources and communication resources. In [START_REF] Henkel | Dynamic resource management for heterogeneous many-cores[END_REF], the authors have introduced a hybrid application mapping that combines design-time analysis with run-time mapping in the context of dynamic thermal and reliability-aware resource management. Most of the available methods focus on determining the suitable mapping of tasks before starting the execution of the application [START_REF] Kaushik | Computation and communication aware run-time mapping for NoC-based MPSoC platforms[END_REF], [START_REF] Maqsood | Dynamic task mapping for network-on-chip based systems[END_REF], [START_REF] Mendis | Dynamic and static task allocation for hard realtime video stream decoding on nocs[END_REF], [START_REF] Rapp | Neural network-based performance prediction for task migration on S-NUCA many-cores[END_REF], [START_REF] Paul | Adaptive task allocation and scheduling on NoC-based multicore platforms with multitasking processors[END_REF], [START_REF]A hybrid adaptive strategy for task allocation and scheduling for multi-applications on NoC-based multicore systems with resource sharing[END_REF]. The mapping of actors is also an active topic for other target platforms like Coarse-Grained Reconfigurable Arrays (CGRA) [START_REF] Li | Chordmap: Automated mapping of streaming applications onto CGRA[END_REF] or Field Programmable Gate Array (FPGA) [START_REF] Huff | Clockwork: Resource-efficient static scheduling for multi-rate image processing applications on FPGAs[END_REF]. This research work addresses the problem of reconfiguring at run-time and at the application level the mapping of dataflow actors on heterogeneous processors. In this work, heterogeneous means that processors share the same instruction set architecture (ISA) while having different coprocessors and different clock domains. The proposed method, which is called run-time remapping, relies on continuous monitoring of exact performance metrics such as the computational time and communication time during real-time execution of the application. Accordingly, a new mapping of the involved actors is determined at run-time targeting the enhancement of the overall performance. This approach is sequentially repeated while the application is running. The application is neither suspended nor modified. The proposed remapping method meets with the dynamic behavior of dataflow applications. Static or offline mapping methods cannot capture the dynamic behavior and thus may not lead to optimal solutions. Also, on-the-fly and hybrid mapping methods suffer from a lack of means to monitor the performance and remap the actors accordingly. In order to apply the proposed method, the architecture of NoCs must be augmented to efficiently provide new services of monitoring performance metrics and remapping the actors, which are not available in conventional networks.

Adopting the devised remapping method and NoC-based architecture leads to balancing the workload. The obtained results show that the adoption of the remapping method reduces the standard deviations of the computational times and communication times of involved processors by 38.58% and 69% respectively. Thus, the variation of the use rate of processors is reduced compared to running the application without remapping. In addition, a reduction of 8.6% in the total execution time has been achieved as well as a reduction of 21% in the number of packets' hops is recorded when comparing to the execution without remapping.

In this paper we introduce three contributions:

• First, we optimize for a NoC-based architecture with het-erogeneous processors, a new run-time remapping (RR) algorithm based on the Move Based (MB) method [START_REF] Ngo | Move based algorithm for runtime mapping of dataflow actors on heterogeneous MPSoCs[END_REF], which allows only one actor to move at a time from one processor to another. Our solution is then compared with state of the art methods for dataflow architectures. • Second, we present new NoC services that allow to implement the observation and adaptation mechanisms. • Finally, we demonstrate our solution with a full implementation of MPEG4-SP, which is available as a reference of a typical dynamic dataflow application. It is also complex enough to exhibit data-dependent execution and communication times. We consider a SystemC packet cycle-accurate NoC simulator to fully decode reference videos and demonstrate the effectiveness of the adaptation mechanism with a real-life dataflow application. The rest of the paper is organized as follows. Section II presents the related work. Section III illustrates the adopted architecture model. Section IV describes the processing flow. Section V details the conducted experiments and presents the obtained results. Finally, Section VI concludes the paper.

II. RELATED WORK

The question of mapping parallel applications on multi or many-core architectures is a very wide problem, with a large number of dimensions, including the programming model, the target architecture (homogeneous or heterogeneous, bus-based or NoC-based, etc.), and the optimization goal (throughput, execution time, energy, etc.) [START_REF] Singh | Mapping on multi/many-core systems: Survey of current and emerging trends[END_REF]. The interested reader can refer to the paper gathering different mapping strategies for NoC-based architectures [START_REF] Sahu | A survey on application mapping strategies for Network-on-Chip design[END_REF]. Following the taxonomy proposed in [START_REF] Singh | Mapping on multi/many-core systems: Survey of current and emerging trends[END_REF], the mapping problem can be solved based on two main strategies: design-time, and run-time. When solved at design-time, the mapping is called static since it's computed offline and does not change while the application runs. This approach allows for exact methods to find an optimal solution [START_REF] Huang | A scalable and adaptable ILP-Based approach for task mapping on MPSoC considering load balance and communication optimization[END_REF] [5] [START_REF] Li | Chordmap: Automated mapping of streaming applications onto CGRA[END_REF], but suffers from a lack of flexibility since it cannot capture the dynamic behavior of some applications. Moreover, even in the case of deterministic execution times of actors in a static context, the paper [START_REF] Rubattu | Pathtracing: Raising the level of understanding of processing latency in heterogeneous mpsocs[END_REF] interestingly shows the difference between the optimal mapping obtained from a well-formalized problem and the real execution trace, due to execution variabilities coming from the hardware.

The dynamic workload should be handled using run-time techniques. The run-time mapping strategies can themselves be divided into two categories: on-the-fly mapping, or hybrid mapping. On-the-fly mapping techniques are application-and platform-agnostic and solve the problem online. Very simple and efficient heuristics should be used to shorten the response time. For NoC-based MPSoCs, various fast heuristics targeting the reduction of communications under constraints have been already proposed [START_REF] Chou | Run-time task allocation considering user behavior in embedded multiprocessor networks-on-chip[END_REF] [23] [START_REF] Fattah | Adjustable contiguity of run-time task allocation in networked many-core systems[END_REF]. These approaches consider one task per core. Allowing multiple tasks on one core is considered in [START_REF] Maqsood | Dynamic task mapping for network-on-chip based systems[END_REF]. Heuristics are fast but can be far from optimal solutions, so hybrid approaches have been introduced. They are based on pre-computed optimal solutions for a set of cases. The job is split into two phases: (1) at designtime, a set of solutions is computed, and (2) one solution is selected at run-time. A wide variety of approaches can then be cited: based on traces in [START_REF] Singh | Resource and throughput aware execution trace analysis for efficient run-time mapping on MPSoCs[END_REF], on priority in [26], on scenario in [START_REF] Quan | A scenario-based run-time task mapping algorithm for MPSoCs[END_REF], on previously identified design points in [START_REF] Singh | Accelerating throughput-aware runtime mapping for heterogeneous MPSoCs[END_REF], or on WCET and scheduling in [START_REF] Skalistis | Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees[END_REF]. None of these studies demonstrates its efficiency with real video applications running reference sequences. The proposed real-time mapping reconfiguration method in [START_REF] Henkel | Dynamic resource management for heterogeneous many-cores[END_REF] requires to suspend the currently running application and the manager remaps the tasks at runtime according to scenarios previously defined at design-time based on the evaluation of multiple mappings, optimizing for their resource requirements and power consumption. Finally, a last approach can fall into the family of hybrid mappings, which considers to recompute partially the mapping problem at run-time. This is called run-time remapping. The work presented in this paper follows such an approach for dataflow applications and leverages design-time analysis profiling results to find at run-time a first mapping. The application is then monitored to update the profiling results and a run-time remapping algorithm runs regularly to check if a new mapping would be better than the current one.

Among the innumerable papers dealing with task mapping, we consider run-time methods for dataflow tasks, and have identified a limited number of solutions. In [START_REF] Yviquel | Towards run-time actor mapping of dynamic dataflow programs onto multi-core platforms[END_REF], the mapping is modeled as a graph partitioning problem, and the problem is solved at run-time by METIS tool, based on profiling information obtained by a first run. Though the migration cost of the actors is not taken into account, the results are promising and could be improved if the mapping does not change completely at each iteration. The approach in [START_REF] Ngo | Move based algorithm for runtime mapping of dataflow actors on heterogeneous MPSoCs[END_REF] allows to successively refine the mapping according to the dynamic behavior of the application, by allowing only one actor to move at a time from one processor to the other. This approach assumes dynamic dataflow application and the target architecture is composed of several heterogeneous cores interconnected by a bus or a NoC. The communication cost is computed based on a rough analytical model of the interconnection network, with the loss of accuracy that comes with it, whereas in our work, we consider profiled values gathered automatically by the system, with a finer grain down to the link. In [START_REF] Quan | A hybrid task mapping algorithm for heterogeneous MPSoCs[END_REF], the application is specified with KPN (Kahn Process Network) and the target architecture is a shared-memory based MPSoC, with also a model of the communication channel (bus or NoC). The approach proposes to rely on three main steps: the two usual design-time preparation and run-time mapping steps plus a new customization step. The design time step computes a set of candidates and populates a database. The run-time mapping initialization derives from the candidates a new initial mapping for the given workload. Finally, the run-time customization step incorporates a Scenario-based run-time Task Mapping (STM) algorithm that is applied to find new mapping of tasks when the system detects that an objective is unsatisfied. It first detects the so-called critical task and then identifies why it misses its objectives: either poor locality or load imbalance. In case of poor locality, an algorithm that considers the communication between tasks is used to find a new mapping. In case of load imbalance, a load balancing strategy based on computational demands of the tasks is used. This step produces a new mapping that may move several tasks, which leads to a (re-)mapping overhead.

When focusing on the small subset of the existing work around hybrid and run-time (re-)mapping of dataflow applications on NoC-based architectures, we consider the work presented in [START_REF] Quan | A hybrid task mapping algorithm for heterogeneous MPSoCs[END_REF] for comparison.

III. ARCHITECTURE MODEL

The target architecture is a heterogeneous Multi-Processor System on Chip (HMPSoC) containing several different PEs and shared memories connected with a Network-on-Chip (NoC). Fig. 2 presents the structure of the adopted NoCbased architecture. Our method is scalable and without loss of generality we consider a specific model of architecture which is required for a data-accurate functional simulation with a packet-level time accuracy. The target architecture is a 4 × 4 mesh-based NoC with 32-bit links that interconnects 28 intellectual property (IP) cores including 15 memory modules, 12 PEs and a processing element that acts as a manager (MGR). The PEs and memory modules are technologically independent of the structure of the NoC. They communicate through the network using a network interface (NI). We consider a simple NoC model that employs the wormhole packet switching mode, the deterministic XY routing algorithm, and a flow control policy without virtual channels. The implemented routers have one buffer of 3 flits per input port and use distributed arbitration logic (one arbiter per port). The back-end part of the NI is typical and includes a packet maker/un-maker, which are used to assemble and disassemble the packets, and a priority manager to synchronize packet transmission and reception.

In this work, it is assumed that P E1 imports the incoming streamed data from an Input buffer and P E12 outputs the processed data. Fig. 2 illustrates the buffers in order to communicate with external systems. Each PE has its local memory. It is assumed that there are no restrictions to map any MPEG4-SP application actor to any PE. The used PEs can all work in parallel according to dataflow firing rules. However, some PEs are enhanced by hardware accelerators dedicated to certain functionalities in order to perform them more efficiently. The shared memories are distributed in memory blocks which have a unique NI. From an NoC perspective, the novelty is the introduction of new command packets used as instructions to manage FIFO accesses, broadcast mapping information, collect monitoring data, and the transfer of binary codes. In order to cope with the command packet and associated notification packet concepts, the NIs implement some additional logic modules. The command packets were already proposed in [START_REF] Diguet | Networked power-gated MRAMs for memory-based computing[END_REF] but only produced by the manager and for a specific application.

A. Manager

The manager is a PE dedicated to the following five tasks: (1) map initially the actors on the available PEs, (2) parse the feedback collected data from all modules (memories and PEs), (3) apply the run-time remapping algorithm and selects the actor to be moved (if any), (4) notify the corresponding PEs (looser, gainer, etc.) about the updated mapping and (5) manage the transferring of the binary code corresponding to the moved actor from the shared memory into the cache of the gainer processor.

B. Processing Elements

The target platform includes twelve PEs. All PEs are supposed to be able to execute any of the forty-one actors involved in the MPEG4-SP application. As the number of PEs is smaller than the number of actors, each PE is considered to run more than one actor. Hence, an actor scheduler is required to manage the order of execution of actors. Mainly, in dataflow applications, all schedulers suffer from inefficient polling which leads to useless memory accesses when a scheduling attempt fails. In this work, the well-known roundrobin scheduling technique has been adopted in all PEs. The actors are given the attempt to be executed in a circular order without priority. The PE will execute the allocated actor if there are enough input tokens and enough space in the output FIFOs as specified in dataflow applications.

Furthermore, some PEs are augmented with hardware accelerators in order to perform special functions more efficiently. In this work, we adopt one of the hardware accelerator specification described in previous similar work [START_REF] Ngo | Move based algorithm for runtime mapping of dataflow actors on heterogeneous MPSoCs[END_REF]. Table I shows the list of accelerators adopted in the simulation platform. In addition, the PEs have been specified randomly to operate on different frequencies. Table II shows the randomly chosen operating frequency of all PEs in terms of the NoC operating frequency f .

C. Memory Modules

The tailored platform integrates three types of memory modules. Each module includes a memory block that returns the data allocated at its specified address. Since the PEs and the manager do not recognize the local mapping of stored data in each memory module and in order to remain compliant with any available memory, the typical NI is extended to accommodate the services for managing the addressing and arranging the retrieved output bits into flits. These new functionalities are implemented as additional components in the front-end of the NI corresponding to each memory module type in order to be independent of NoC parameters. In the following the functionalities of each memory type is described. 1) Binary code memory module (BCM): It contains the binary codes of all actors. The manager sends a specific packet request to BCM to forward the binary code of the moved actor to a given PE according to the decision taken after executing the RR algorithm. A simple module, so-called memory address mapper (MAM), is integrated into the NI of the BCM in order to find the correct memory address. For a specific actor, MAM determines the starting address of the binary code and its corresponding size based on the actor's ID and by the means of simple look-up-tables that include the starting addresses and the size of the binary codes of all actors. Furthermore, MAM manages the extraction of data from the memory and delivers it to the packet maker unit.

2) Mapping/Monitoring information memory module (MIM): This memory module accommodates twelve memory blocks. Each block is dedicated to a specific PE and is supposed to store two types of data. The first type is the mapping information, which is generated by the manager and indicates which actors are to be executed by each PE in addition to their supplementary information about input and output FIFOs and the reading orders for each input FIFO (III-D1c). The second type is the monitoring information (III-D1e), which is collected by the PEs during processing a specified number of video frames. Storing the monitoring information overwrites the mapping information, which is not needed by the PEs anymore.

When a packet holding either mapping or monitoring information is received, the MIM module first identifies the corresponding PE. Accordingly, it dissembles the packet and stores the data found in the packet payload into the memory block assigned to the identified PE.

Moreover, the MIM informs the manager about the availability of new monitoring information and the corresponding PE about the availability of new mapping information. To do so, the MIM sends notification packets (III-D1a) as per the concept of notifying memory concept demonstrated in [START_REF] Martin | Notifying memories: a case-study on data-flow applications with NoC interfaces implementation[END_REF]. In addition, the MIM responds to reading requests (III-D1b) sent from the manager to acquire the stored monitoring information from the PEs or to get the new mapping information.

3) Multi-FIFO memory module (MFM): This type of memory module is dedicated to store the data which is either Writing address reaching data size imported to the system or processed by the PEs. Each MFM accommodates a specific number of FIFOs. Only one FIFO is used at once. The inputs of all FIFOs are connected to the module's inputs using demultiplexers whereas the FIFOs' output data ports are multiplexed. This signal is buffered from the value of FIFO address which is specified in the payload of the arriving packets (see Fig. 4). The multiplexer and demultiplexers are added to the adapter in the NI. Moreover, the MFMs receive the following types of packets: (1) FIFO Index packet (III-D1f) that aims either to retrieve or to set the writing and reading indexes, (2) Data Reading Request packet (III-D1g) that demands to read data from a specified FIFO and (3) Data packet (III-D2a) that is used to write data in a specified FIFO.

A simple circuit is integrated into the adapter of the NI in all MFM modules in order to manage the memory addressing for all listed-above packet types. It is composed of a simple controller and two 4-to-1 multiplexers and an adder in order to generate the appropriate address values to be given to the MFM FIFOs. After disassembling the arriving packet, the packet un-maker delivers the packet type and the data size to the controller. Accordingly, the controller generates the control signals to configure the two multiplexers, which are dedicated to select the values of starting address and the offset as listed in Table III. These two values are then added to compute the memory address. In addition, the controller determines the number and type of the required memory accesses. It incorporates a simple comparator and an address counter which is incremented for each required access.

D. Packets' structure

The developed NoC architecture considers two categories of packets: (1) command packets and (2) data packets.

1) Command packets: Command packets are initiated by the cores and processed by the NIs of destination nodes. Several command packets, described hereafter, have been opted in order to manage FIFO accesses, send mapping information, collect monitoring data, and manage the transferring of binary codes.

a) Notification packets (NP): The NPs aim to inform the PEs that new information is ready to be requested. This technique is inherited from the notifying memories (NM) concept presented in [START_REF] Martin | Notifying memories: a case-study on data-flow applications with NoC interfaces implementation[END_REF]. When receiving a NP, the PE will send a reading request to retrieve the available data at the corresponding notifying memory. In this work, notification packets are used either to inform an ordinary PE that new mapping information is available or to notify the manager that updated monitoring information has been generated and stored. The NP has empty payload and aims to trigger the manager and PEs to request data when it is ready rather than frequent inefficient polling.

b) Monitoring/Mapping information reading request packets (MRP): This type of packet is used to request the information stored in the MIM module as a response to the NP. It is either generated by the manager to acquire the new monitoring information sent from a definite PE or by one of the PEs to get the new mapping information provided by manager. For both information types, monitoring or mapping information, the request packet does not include any payload. c) Mapping information packets (M p IP): The manager uses a M p IP to inform all involved PEs after determining or modifying the actor mapping strategy. Its payload includes the following: (1) the number of actors which are mapped to the PE, (2) the IDs of the mapped actors, (3) the IDs of the input and output FIFOs, and (4) the actor reading order in each input FIFO. Fig. 3 illustrates the structure of the packet holding the mapping information.

d) Mapping Confirmation packets (MCP):

A MCP aims to inform the manager that the new mapping information is well received by both the former and the new owner of the actor. The MCP payload is also empty.

e) Monitoring information packets (M n IP): This type of packet holds the feedback information needed by the manager to perform the RR algorithm. Fig. 3 presents the structure of the monitoring information packet.

f) FIFO index packets (FIP): The FIPs are designed to hold the writing indexes or reading indexes of FIFOs. As mentioned before, DF applications rely on a large number of requests to memories for firing rule checking. So, these indexes are used to determine either the number of available tokens corresponding to each reader actor or the free space in a FIFO. If data is required to be read from input FIFOs, the firing rule is satisfied by checking if the number of available tokens in all input FIFOs is equal or greater than the required number during computation. Whereas, if data has to be written to output FIFOs, the firing rule is satisfied by checking if all output FIFOs have sufficient empty room to accommodate the produced tokens. Hence, before processing an action, a PE

Holding read/write index.

As the FIFO may have several reading indexes corresponding to different reader actors, the PE has to determine the reading order of the actor and sends it in the payload of the packet. However, a FIFO has only one writer actor; hence, to attain the value of its writer index the PE has to send the FIFO address in the destination memory module. In both packets, the packet type, given in the packet's header, is used by the NI at the destination memory module to decode the request type. Fig. 4 depicts the structure of the FIP packets holding the requests of a reading index and writing index.

On the other side, whenever a memory module receives a request of reading/writing index it will retrieve its value from the specified FIFO and sends it back to the PE. The NI in the memory module will assemble a 1-flit payload packet as shown in Fig. 4.

In order to set the reading/writing index after finalizing the data transfer operations from/to a FIFO, the PE sends a control packet that notifies the FIFO about its new reading/writing index. It includes one flit that contains the FIFO address in the destination memory module, the reading order of the actor, and the new value of the reading index. Since the FIFOs have only one writer actor, the writing packet payload simply includes the address of the targeted FIFO in the destination memory module and the new value of the writing index.

g) Data reading request packets (DRP): Fig. 5 presents the packet holding the reading request of data from PE to memory module. Its payload consists of one flit that includes the address of the FIFO in the destination memory module, the starting address of reading, and the size of required data. be transferred from the shared memory to the cache of the new PE. The manager sends a command of transferring the binary code in the form of a reading request packet. The sent request includes the actor ID, the address of the new PE, and the size of transferred data per packet (see Fig. 6).

2) Data packets: The second category of packets refers to the ordinary flow of data between PEs and memory modules. These packets, described hereafter, carry data that is either processed in a PE and written in a memory module or sent from a memory module as a response to a PE reading request.

a) Dataflow packets (DFP): The DFPs encompass all packets transferred between PEs and the FIFOs distributed in the memory modules. They carry data that is either processed in a PE and will be stored in a FIFO or sent from a FIFO as a response to a PE reading request. Fig. 7 presents the structure of packets carrying processed data in their payloads.

b) Binary code packets (BCP): The BCPs aim to transfer the binary code from the shared memory to the cache memory of the new PE. Note that the binary code is divided into sections of reasonable sizes which are transferred consequently. The size of the transferred data (payload capacity) is specified by the manager according to the monitored traffic in the network and based on the required cache lines to be filled before launching the actor on the new PE. For example, the packet including in its payload 64 flits of 32-bitwidth transfers 256 bytes which form 4 lines of L1 cache.

IV. PROCESSING FLOW A. Initial mapping

Initially, the actors are mapped randomly to the PEs, or can be mapped using the exact method presented in [START_REF] Huang | A scalable and adaptable ILP-Based approach for task mapping on MPSoC considering load balance and communication optimization[END_REF]. FIFOs are mapped randomly and are approximately equally distributed on all memory blocks. The manager informs by means of packets all involved PEs. For each PE in charge of executing actors, the manager generates and sends its corresponding mapping information in a separate packet (M p IP). Packets holding the mapping information are stored in a predefined location in MIM. Then, the involved PEs are notified to retrieve their mapping information from the shared memory using notifying packets. At this stage, the manager waits the PEs, which are incorporated in processing a specific number of video frames N F to send their monitoring information. Note that N F is set originally to a default value and may be changed dynamically by the manager. Before receiving the notification packet about initial mapping of actors, all PEs are in idle state. Once it receives the notification packet, the PE sends a request to retrieve the mapping information which includes IDs of actors to be executed, IDs of input and output FIFOs for each actor, and the reading order of each input FIFO. The mapped actors are scheduled according to the order sent from the manager and the PE begins to execute them in round-robin manner.

B. Monitoring actor execution

The execution of actors continues until receiving a new notification packet about changing the mapping information. All involved PEs monitor their running actors during the processing of N F video frames, which determine the observation window. Precisely, each PE node accumulates for every mapped actor A c its communication time T cm [A c ], computation time T cp [A c ], and total number of tokens received to each input port N T total [A c [I j ] ] where c ∈ {1, ..., |A|} and j ∈ {1, ..., |I c |}. In addition, the adapter, which is embedded in the NI of each node n (processor or memory), extracts from each received packet carrying processed data, the following information for each source S i : (1) the total number of transferred tokens from S i to n: N T n total [S i , n] and (2) the average time delay consumed per token to reach the node n from source S i : T av [S i , n].Table IV gathers the variables and parameters used to formalize our mapping approach.

The total number of transferred tokens is simply determined. First, input packets are classified according to their sources S i . Then, their corresponding sizes size P k [S i ], which reflect the number of data-flits, are accumulated.

N T n total [S i , n] = K k=1 size P k [S i , n] (1)
where i ∈ {1, ..., |P| + |M|}.

The average time delay per token per each source T av [S i , n] is calculated by dividing the time delay of each token transferred from

S i by N T total [S i , n]. T av [S i , n] = K k=1 size P k [S i , n] × D P k [S i , n] N T n total [S i , n] (2)
where k ∈ {1, ..., |K|}.

D P k [S i
] is determined by embedding, at the source node, for each packet P k its sending time-stamp T s [P k ] in its header then subtracting it from the reception time T r [P k ] at the destination node. All tokens in a packet are considered to have the same delay.

D[P k ] = T r [P k ] -T s [P k ] (3)

C. Collecting monitoring information

When the number of the processed frames meets the observed window, each PE node generates its own monitoring information packet. The packet is then sent to the MIM module (presented in III-C). Directly, the accumulated values are reset with the beginning of the new observation window. Then, the PE continues executing the previously mapped actors according to the adopted circular order. This guarantees that the remapping does not impose any additional overhead in terms of latency. The MIM module notifies in its turn the manager when new monitoring data is available corresponding to a specific processor throughout a notification packet (III-D1a). Whenever a new notification packet is received by the manager, the latter directly requests to retrieve the new available monitoring data. Also, the manager requests using command packets from all memory modules to send their monitoring information. Note that memory modules respond to the manager and send the requested data directly without any notification process since the adopted MoC allows the direct communication between a memory and a processor. All received monitoring packets are disassembled and their contents are parsed and saved in the manager local registers.

When the feedback data is collected from all modules incorporated in processing the video frames, the manager applies the run-time remapping algorithm. At this stage, the manager owns locally the following data:

D. Estimating NoC communication time delay

Communication time delay is a critical factor in HMPSoC platforms using NoCs. The communication time of the moved actor is affected by the location of the new hosting PE in the network. NoC time-delay estimation impacts directly the prediction process of the communication time of the moved actor. Hence, the accuracy level in estimating the delay latency changes the decision on the actor move in the RR algorithm. In this work, two novel methods have been proposed to estimate the communication time delay for transferring one token in the 1) Average-path token delay (APTD): In this approach, a path is considered to be formed from the set of the interconnections between two specific nodes. As an example, Fig. 8 illustrates in red the path P [P E1,M F M6] between processing element P E 1 to memory module M F M 6 . As a deterministic routing is applied in this work, the packets always use the same path between the source node and the destination node. Since the adopted MoC forbids the transfer of packets in between memory modules and in between PEs, the active paths are those connecting either memory modules to PEs or PEs to memory modules. Note that the packets transferred from a processing element p to a memory module m do not follow the same path used in transferring packets from the memory module m to the processing element p. Fig. 8 illustrates in red the followed path to transfer packets from P E 1 to M F M 6 and in yellow the followed path to transfer packets from M F M 6 to P E 1 . In APTD, the manager calculates the average path delay per token T av in several steps as shown in Algo. 1. T av refers to the average time delay required to transfer one token from the source node to the destination node, regardless of the path between the source and destination nodes. As an example, the average time delay of all tokens transferred through either the path P [P E1,M F M6] or the path P [M F M6,P E1] (Fig. 8) is considered equal regardless of the number of links constituting each path and the corresponding traffic in each link and the switch conflicts in the connecting routers. T av is computed by dividing the sum of the communication-time delays D total by the total number of transferred tokens in the network N T total :

T av = D total N T total (4)
The manager benefits from the collected monitoring data. It makes use of the number of input tokens N T n total [S i , n] transferred to each destination node n from each source node S i to determine the total number of all transferred tokens in Algorithm 1 Average-path token delay (APTD)

Step 1: Find the sum of the communication delays D total

Step 2: Find the total number of all tokens N T total

Step 3: Calculate the average time delay per token T av the network (N T total ) as presented in (5):

N T total = |P|+|M| n=1 |P|+|M| i=1 N T n total [S i , n] (5)
Also, the communication-time delays for all tokens transferred in the network are accumulated. The sum of the communication delays D total is determined according to (6):

D total = |P|+|M| n=1 |P|+|M| i=1 T av [S i , n] × N T n total [S i , n] (6)
where T av [S i , n] is the collected average time delay required to transfer one token from the source node S i to the destination node n.

2) Average-link token delay (ALTD): A link is defined as the interconnection between two consecutive components of the NoC: Router, Memory and PE. As an example, Fig. 8 shows the links constituting the path P [P E1,M F M6] . In this approach, the average communication time delay per token is determined for each link as shown in Algo. 2. The total communication-time delay in a path P [Si,n] connecting the source node S i and the destination node n is determined from the monitored data as shown in [START_REF] Wang | Dynamic application allocation with resource balancing on NoC based many-core embedded systems[END_REF]:

D P total [S i , n] = T av [S i , n] × N T n total [S i , n] (7)
Each path is segmented into a set of links L P [S i ,n] . The average communication time delay per link D L av [S i , n] in the path P [Si,n] is determined as follows:

D L av [S i , n] = D P total [S i , n] N L[S i , n] (8)
where N L[S i , n] is the number of links constructing the path P [Si,n] . Here, the links constructing a path are assumed to have similar contribution in the total communication time delay monitored in the path. As a link l is shared among different paths, the total link communication-time delay D total [l] is the sum of all average communication-time delay per link computed in all paths in which link l constitutes one of their interconnections:

D total [l] = |P|+|M| n=1 |P|+|M| i=1 D L av [S i , n] ∋ l ∈ L P [S i ,n] (9)
On the other hand, the tokens passing through a path are definitely passing through all links constructing the path. Hence, the total number of tokens N T total [l] passing through a link l is the sum of all tokens passing through all paths, which link l constitutes one of their interconnections:

N T total [l] = |P|+|M| n=1 |P|+|M| i=1 N T total [S i , n] ∋ l ∈ L P [S i ,n] (10
T av [l] = D total [l] N T total [l] (11)

E. Applying RR algorithm

For each observation window (N F frames), the manager executes at run-time the RR algorithm, which is divided into two main steps. The first step is dedicated to find all possible candidate actors which their moves would enhance the overall throughput. The second step sets a tradeoff between the cost of migration and the predicted improvement of the performance.

1) Specify the possible candidate actors: In this work, the definitions of the terms period of each processor p (P eriod p ), maximum period (P eriod max ) and throughput (T h) have been adopted as introduced in [START_REF] Ngo | Move based algorithm for runtime mapping of dataflow actors on heterogeneous MPSoCs[END_REF]. P eriod p is the sum of total computation time compT p and total communication time commT p recorded during N F video frames:

P eriod p = compT p + commT p ∀p ∈ P (12)
where compT p and commT p of processor p are the sums of the computation times and of the communication times respectively of all actors which are mapped on this processor:

compT p = k:P[k]=p T cp [A k ] ∀p ∈ P (13)
commT p = k:P[k]=p T cm [A k ] ∀p ∈ P ( 14
)
The throughput is defined as the inverse of the maximum period over all processors. Hence, the first task is to find the PE with the maximum period. The manager computes the periods of all PEs during the current observation window of N F video frames. Later, a simple comparison between all obtained period values is performed in order to specify the processor with the maximum period. The processor with the maximum period (P eriod max ) is nominated as looser processor. The algorithm used to determine the looser processor is outlined in Algo. 3. The set of candidate actors to be moved C includes the actors that have been previously executed by the looser processor. Fig. 9 demonstrates an example of P eriod p and P eriod max . The figure shows three PEs (P E 1 , P E 2 and P E 3 ) that run six actors (A 1 , A 2 , A 3 , A 4 , A 5 and A 6 ). In this example, P E 1 has the largest period, thus it is selected as the looser processor.

Algorithm 3 Finding processor with maximum period P eriod max ← 0 looser ← ϕ for p ∈ P do if P eriod max < P eriod p then P eriod max ← P eriod p looser ← p end if end for 2) Decision of the actor move: The actor selected to be moved should have a maximum total gain. According to the collected monitoring values, the manager estimates the total gain achieved for all combinations of mapping the actors which belongs to the candidate list C onto all available PEs. The estimated total gain Gain e total [C Ac,p ] of a mapping combination C Ac,p , which corresponds to moving A c to p, is computed by finding the difference between the estimated performance gain Gain e per [C Ac,p ] and the estimated migration cost of the actor Cost e mig [C Ac,p ]. The mapping combination that leads to the maximum estimated total gain is then selected. The engaged processor and actor are specified and so-called the gainer processor and moved-actor respectively. a) Estimated performance gain: For each actor A c in the candidate list C, the manager considers it is moved virtually to all PEs except the looser processor. For each virtual-move combination, the manager estimates the achieved period of each processing element P eriod

) Note that the tokens, which are consumed by a certain reader actor running on a processing element P E R , are imported from a FIFO f . These tokens are previously generated by another actor running on another processing element P E W . The generated tokens are first stored in a FIFO f and then transferred once requested to the processing element P E R where the reader actor is executed. Hence, the tokens pass

𝑃𝑒𝑟𝑖𝑜𝑑 𝑃 1 𝑃𝐸 1 𝑇 𝑐𝑝 [𝐴 1 ] 𝑇 𝑐𝑚 [𝐴 1 ] 𝑇 𝑐𝑝 [𝐴 2 ] 𝑇 𝑐𝑚 [𝐴 2 ] 𝑇 𝑐𝑝 [𝐴 3 ] 𝑇 𝑐𝑚 [𝐴 3 ] 𝑃𝑒𝑟𝑖𝑜𝑑 𝑃 2 𝑃𝐸 2 𝑇 𝑐𝑝 [𝐴 4 ] 𝑇 𝑐𝑚 [𝐴 4 ] 𝑇 𝑐𝑝 [𝐴 5 ] 𝑇 𝑐𝑚 [𝐴 5 ] 𝑃𝑒𝑟𝑖𝑜𝑑 𝑃 3 𝑃𝐸 3 𝑇 𝑐𝑝 [𝐴 6 ] 𝑇 𝑐𝑚 [𝐴 6 ]
𝑃𝑒𝑟𝑖𝑜𝑑 𝑚𝑎𝑥 𝑡𝑖𝑚𝑒 Fig. 9. An example of P eriodp and P eriodmax through two paths. The first path P [P E W ,M F M f ] connects the processing element P E W , which executes the writer actor, and the memory module that accommodates the FIFO f . On the other hand, the second path P [M F M f ,P E R ] connects the memory module that accommodates the FIFO f and the processing element P E R which executes the reader actor. The communication-time delays in both paths are considered when estimating the communication time of the moved actor. When adopting APTD method for determining the communication delay in the NoC, the estimated communication-time delay per input j for each actor A c is equal to the total number of input tokens N T total S[A c [I j ] ] transferred to the actor at this input multiplied by the double of the calculated average path communication-time delay per token T av (4). The average path delay per token is doubled to compensate the time delay of the two paths

P [P E W ,M F M f ] and P [M F M f ,P E R ] .
The total estimated communication time is the sum of all estimated communication-time delays of all inputs:

T e cm [C Ac,p ] = |Ic| j=1 2 × T av × N T total [A c [I j ] ] (16)
Note that the adopted model of computation forbids the transfer of tokens in between actors (running on PEs) directly without passing through a FIFO (allocated in a memory module M F M f ). Hence, tokens produced by the writer actor (running on P E W ) will pass through two paths (P

[P E W ,M F M f ] and P [M F M f ,P E R ]
) before arriving to the reader actor (running on P E R ). The exact number of tokens passes through both paths while considering same average path delay per token T av . So, the average path delay per token is doubled in [START_REF] Huff | Clockwork: Resource-efficient static scheduling for multi-rate image processing applications on FPGAs[END_REF]. When adopting ALTD method, the estimated communication-time per input j is equal to the total number of input tokens N T total [A c [I j ] ] transferred to the actor A c through this input multiplied by the sum of all average communication-time delay per token T av [l] for each link l constructing the paths which the input tokens use to reach the processing element running the actor A c . The total estimated communication time will be the sum of all estimated communication-time delays of all inputs:

T e cm [A c ] = |Ic| j=1 i=1 T av [l i ] × N T total [A c [I j ] ] ∋ l i ∈ L P [P E W ,M F M f ] ∪ L P [M F M f ,P E R ] (17)
In addition, the estimated computation time T e cp [C Ac,p ] of the moved actor A c is determined depending on the recorded computation time of the moved actor A c during the previous mapping T cp [A c ] and the estimated total speed-up ratio SU e total [C Ac,p ], which is achieved when moving A c to p:

T e cp [C Ac,p ] = T cp [A c ] × SU e total [C Ac,p ] (18)
such that

SU e total [C Ac,p ] = A Ac [p] A Ac [looser] × f [looser] f [p] ( 19
)
where f [p] is the operating frequency of processor p (Table II) and A Ac [p] is the acceleration enhancement ratio of the moved actor A c when running on processor p (Table I).

Note that for all mapping combinations, the period of the looser processor is modified when an actor A c is supposed to be mapped to another processor p. Hence, it is updated by subtracting the actual communication time T cm [A c ] and the actual computation time T cp [A c ] of the moved actor A c :

P eriod e looser [C Ac,p ] = P eriod max -T cm [A c ]-T cp [A c ] (20)
For each mapping combination, the manager determines the maximum estimated period P eriod e max [C Ac,p ] which denotes the maximum period among all processors when actor A c is mapped to processor p. These computed new periods are then used to find the performance gain related to each mapping combination:

Gain e per [C Ac,p ] = P eriod e p [C Ac,p ] -P eriod max (21) b) Estimated migration cost: The migration cost of an actor is the required time to transfer its binary code into the local memory of the new hosting processing element. It depends on the size of the binary data required to be transferred and the communication-time delay in the network. The sizes of the binary codes of all actors are considered to be known by the manager in terms of number of flits. Accordingly, the migration cost of the moved actor is estimated by the manager using the estimated NoC communication-time delay. When adopting APTD method, the estimated migration cost related to the moving of actor A c to processor p is calculated as expressed in [START_REF] Chou | Run-time task allocation considering user behavior in embedded multiprocessor networks-on-chip[END_REF]:

Cost e mig [C Ac,p ] = size bin [A c ] × T av (22)
where size bin [A c ] is the size of the binary code of actor A c and T av is the average path communication-time delay per token (4). When ALTD method is adopted, the migration cost of the moved actor A c is determined by [START_REF] Carvalho | Dynamic task mapping for MPSoCs[END_REF]:

Cost e mig [C Ac,p ] = size bin [A c ] × i=1 T av [l i ] ∋ l i ∈ L P [BCM,p] (23)
c) Estimated total gain: The manager computes the total gain estimated to be achieved for all mapping combinations by finding the difference between the estimated performance gain Gain The moving of an actor would lead to permanent performance gain and the migration cost is paid once. However, the estimated performance gain takes the cost of migration into account in order to aggravate the probability of enhancing the overall performance directly after applying the move (in the next observation window). In fact, the variation of the input data and its corresponding effects on executing the 𝑡𝑖𝑚𝑒 Fig. 10. An example of finding the maximum periods for each mapping combination involved actors incites to consider worst case (severe) decision where the performance enhancement should be guaranteed once moving the actor. Then, the manager finds the maximum achieved total gain among all mapping combinations and accordingly specifies the actor to be moved and the gainer processing element.

F. Moving the actor to the gainer processor

The PE, after finishing the execution of the current running actor, retrieves the new mapping information and sends directly a confirmation packet so that the manager processor manages the transfer of the object code corresponding to the new mapped actor. Before running the moved actor, the Algorithm 4 Run-time Remapping (RR)

Step 1: Calculate the period of each PE

Step 2: Find PE with Max. period and assign it as looser

Step 3: Find the total gain (performance -migration cost) for each move do a-Find the performance gain . find the period for each PE . find the maximum period b-Find the migration cost c-Calculate the total gain end for Step4: Choose the move with Max. positive total gain PE checks the availability of the object file corresponding to the actor in its cache memory. Note that for the initial mapping, the manager generates and sends packets to all PEs in charge of executing actors. Whereas, after executing the RR algorithm, the manager informs only the gainer and looser processors. This procedure reduces the traffic in the network and maintain the processing performance since the PEs that are not affected by remapping process are not disturbed. In fact, the manager informs first the looser processor about the new mapping information. Then, it waits until the looser processor confirms the well reception. The looser processor sends a confirmation packet to the manager whenever it finishes the execution of the moved actor. When the manager receives the confirmation packet, it sends the new mapping information to the gainer processor. Later, the gainer sends a confirmation packet to the manager that directly manages the transferring of the object code of the mapped actor from the shared memory into the cache memory of the gainer processor by making use of BCPs described in subsection III-D2b. This guarantees that the actor is executed by only one PE in the whole platform and ensure better controlling of the traffic while migrating the binary codes. In fact, the manager sends a CTP (subsection III-D1h) which includes the ID of the gainer processor, the ID of the moved actor and the size of the BCPs (capacity) as described in subsection III-C1. After receiving the CTP, the MAM module, which is integrated into the NI of the BCM (subsection III-C1), manages retrieving the binary code from the shared memory and dividing it into sections according to the capacity specified by the manager. The generated BCPs will be transferred to gainer processor. In our work, we consider that the gainer processor can start executing the actor once at least 256 bytes, which construct 8 lines of the L1-I cache, are received and stored to the gainer processor local memory. The hierarchy of the PEs' local memories includes L1 and L2 caches. L1 cache is broken up into to halves, instruction (L1-I) and data (L1-D) each of 32KB. L2 cache size is of 256KB and is used for instructions and data.

G. RR Algorithm Complexity

The devised algorithm consists of several steps summarized in Algo. Note that the algorithm is computed when all monitoring data is collected, so the maximum rate is once per execution of the whole data flow, and in practice can be tuned to be slower. With respect to the complexity and the execution rates of actors, this complexity is extremely low.

V. EXPERIMENTS AND RESULTS

A. Application Model

In this work we target the multimedia application domain. We adopt the well-known MPEG4 part 2 Simple Profile video decoder (MPEG4-SP). This multimedia application is typically used in de-compression of encoded video digital data. Fig. 11 presents the structure of decoder as described in Reconfigurable Video Coding framework (RVC) [3] [33].

MPEG4-SP is specified with heterogeneous dataflow MoCs and includes up to 40% of dynamic actors [START_REF] Wipliez | Classification of dataflow actors with satisfiability and abstract interpretation[END_REF]. It is composed of 41 actors and 70 FIFOs specified in RVC-CAL language. The ORCC tool is utilized for compiling and software synthesis [START_REF] Yviquel | Orcc: Multimedia development made easy[END_REF] and we make use of the generated C-code for multicore platforms. We also use the structure of the software FIFO presented in Fig. 1-b), which is generated by ORCC.

A FIFO may have several reader actors but only one writer actor. It opts an indexing mechanism such that a specific index is assigned to each reader or writer actor. These indexes are used to determine the number of available tokens corresponding to each reader actor and the free space in a FIFO. The number of available tokens (T f [R i ]) in a FIFO (f ) is the difference between the reader index (I f [R i ]) and the writer index (I f [W ]). The free space in a FIFO is the number of memory addresses that contain no more needed data from all reader actors. In other words, it is the subtraction of the maximum available tokens from the total FIFO size (Size f ).

Each actor has its input and output ports and includes one or several actions. An action describes a specific functionality and is executed (fired) when a set of conditions, so-called firing rules, are satisfied. As an example, a firing rule consists of checking if the number of available tokens in the input FIFO is greater than the required number for computation, and that the output FIFO has sufficient empty room to store the produced tokens. In MPEG4-SP, the number of reader actors ranges from 1 (at least) to 6 (at most).

MPEG RVC defines RVC-CAL applications as dynamic dataflow applications, where the uncertainty of computing due to data-dependency prevents from any static scheduling. They are based on dataflow process network (DPN) model [START_REF] Lee | Dataflow process networks[END_REF]. In such model, the actor executes when at least one of its firing rules is satisfied. For cases where several firing rules Fig. 11. MPEG4 part 2 SP decoder [START_REF] Bhattacharyya | Overview of the MPEG reconfigurable video coding framework[END_REF] are satisfied simultaneously, only one is selected according to its priority. Consequently, its corresponding satisfied action is fired. Each firing consumes input tokens and produces output tokens. The number of the consumed or produced tokens may be fixed or variable.

B. Experimental framework and setup

In order to assess the feasibility of our proposed runtime remapping method, we developed a real-time simulator. The simulator is described in SystemC TLM model [START_REF] Grotker | System Design with SystemC[END_REF]. The devised simulator models a MPSoC platform using NoC concept for interconnecting embedded modules. The platform incorporates heterogeneous processing elements (Table I), memory blocks, and the manager. The simulator platform has been designed with hierarchical modules that can work concurrently and intercommunicate via ports using simple or complex communication channels. SystemC features have been exploited to mimic the accurate functionality of the modules described in section III. The adopted NoC-based architecture, presented in section III, is implemented in the devised simulator platform. In order to accurately model the adopted application, all involved actions are functionally simulated to determine their executiontiming features and generate the real data exchanged by actors during video decoding. The SystemC model adopted in the simulation platform is cycle accurate at the level of the NoC and the network interfaces. The timing of all corresponding action executions on PE is compensated in the simulation according to the profiling data extracted while running the application on a reference computer. Profiling data provides, for each involved action, the mean value of the number of cycles required to execute it. In this work, profiling data has been extracted using on a desktop computer (i7-2620M CPU@2.7 GHz and 8GB memory). We consider that the NoC operating frequency f is 500 MHz. The clock cycle in each PE is determined according to Table II. During SystemC simulations, for each fired action, its corresponding execution time determined in profiling is mapped according to the processor frequency and used as time delay to compensate the real execution time. In addition, several benchmark video sequences with different formats from [START_REF]in Signal, Telecom, Image, and Speech from the Lebanese University in 2007[END_REF] have been encoded. The selected video sequences have different manner in changes between successive frames. This guarantees to evaluate the performance of the proposed algorithm for different datadependent behaviors. The resultant data has been used as input to the decoder. These same encoded videos have been Total Control Fits Total Data Flits Fig. 12. Classification of transported packets and flits decoded on a desktop computer and the FIFO contents have been traced over the decoding period. To verify the proper functionality of each actor, the contents stored in the FIFOs in the simulator have been compared to the traced FIFO data. Also, the output data of the simulator have been reconstructed into visual video in order to verify the functionality of the devised simulator. The video sequences have been decoded without applying remapping targeting the same NoC-base architecture and the obtained results have been compared to that obtained when the video sequences are decoded adopting the MB remapping algorithm applying ALTD and APTD for estimating the communication time delay while considering an observation window of N f = 10.

C. Experimental Results

1) Transported data:

The number of packets that travel through the network during the decoding of the video sequences, and their corresponding flits are recorded in the case of applying the MB remapping and the case of decoding the video without remapping. Fig. 12 presents the number of transported packets and flits in logarithmic scale during decoding the Foreman video with CIF format and Bus video with QCIF format for the case of adopting MB remapping algorithm and the case of ordinary decoding. The packets and flits are classified into control and data categories. The figure shows that the flits of control packets form about 53% of all transported flits in the two cases.

Furthermore, investigating thoroughly the types of transported control flits illustrates that 93% of control flits belong to FIP. This refers to the MoC adopted in dataflow applications which requires checking the firing rules (availability of input data and output buffer space). Fig. 13 shows in logarithmic scale the number of each type of control flits transported while decoding the Foreman video sequence in CIF format and Bus video sequence in QCIF format for the case of MB remapping and the case of ordinary decoding. Also, Fig. 13 shows that additional flits are transported in the network due to the remapping. In fact, applying remapping induces additional control and data packets. In order to evaluate the effect of applying the MB remapping algorithm on the traffic in the network, the transported flits are classified into two main categories. The first category includes the flits which are used basically for dataflow. This category encompasses the flits which occupy the payload of all FIP, DRP and DFP. The second category includes the induced flits by applying the remapping algorithm. Hence, the second category compromises the flits listed in the payloads of NP, MRP, MCP, M n IP, M p IP, CTP, and BCP. Note that both categories include data and control packets. Fig. 14 illustrates the comparison summary in terms of the number of transported flits of both categories. In the figure, the number of transported flits, which is obtained while processing the Foreman video with CIF format and Bus video with QCIF format, is presented in logarithmic scale for both cases (decoding while applying remapping algorithm and ordinary decoding). The comparison shows that the additional flits induced by applying the MB algorithm forms less than 0.02% from total transported flits.

In addition, Table V shows the percentage of flits transporting the binary code of migrated actors from the total number of transported flits in the network while decoding several video sequences. The presented percentages illustrate that the impact of actor migration on the traffic is negligible.

2) Packet time-delay: The packet time-delay is recorded while decoding the video sequences, following the procedure explained in subsection IV-B. Fig. 15 presents the variation of the sum of packet time-delays throughout the observing windows during the decoding of the Foreman video sequence with CIF format when adopting the MB remapping technique.

It is noticed that applying the MB remapping algorithm affects the time-delay of the packets. In addition, the figure shows the comparison with the case of ordinary decoding. The comparison illustrates that using MB remapping decreases gradually the total packet time-delay. Note that the task moves occur after processing 80, 100, 160, and 270 frames. Fig. 15 shows that the total packet delay decreases after the conducted moves. This refers to the fact that task remapping contributes in distributing the tasks on PEs that are nearer to the memory modules accommodating the input and output FIFOs. Also, Fig. 15 presents a comparison in terms of average time-delay of packets transported during the decoding of the Foreman video with CIF format when adopting the MB remapping technique and when using ordinary decoding. The comparison confirms that the use of MB remapping technique contributes significantly in reducing the time-delay.

3) Timings: Fig. 16 presents the recorded total communication time and total computational time throughout the observing windows during the decoding of the Foreman video with CIF format when adopting the MB remapping technique and when using ordinary decoding. It shows that the communication time represents 90% of the total execution time in both cases. Hence, the total execution time is affected more by the variation of the total communication time. Also, Fig. 16(a) shows that the total communication time is almost not changing among observation windows in the case of ordinary decoding. Whereas, when MB technique is applied, the communication time varies significantly and tends to follow a decreasing manner as shown in Fig. 16(b). This illustrates that reducing the time-delay achieved by MB remapping has a direct impact on the communication time.

The communication time of each processing element is investigated through the decoding of all video frames. It is noticed that when applying the MB remapping technique, the variation between communication times of all involved PEs is reduced. The communication time values of all PEs converges gradually to a specific interval as shown in Fig. 17.

4) Performance results: Multiple simulations have been conducted to decode several benchmark video sequences from [START_REF]in Signal, Telecom, Image, and Speech from the Lebanese University in 2007[END_REF]. Fig. 18(a) presents the achieved throughput in terms of frames per second (FPS) when decoding Foreman video (CIF format) and using ALTD and APTD respectively for estimating the NoC communication time delay. The figure also shows the achieved throughput when decoding the Foreman video (CIF format) without remapping. The letter "M" shown on the curves represents when an actor move occurs. Fig. 18(a) shows that using MB results in significant performance enhancement. In addition, the figure illustrates that adopting ALTD for estimating the NoC communication time delay, while decoding Foreman video sequence with CIF format, increases the achieved enhancement ratio. Other similar simulations have been conducted targeting other video sequences with different formats (CIF, 4CIF and QCIF). The selected videos are of diverse characteristics to ensure that the proposed remapping algorithm is not related to specific formats or video content. The obtained results confirm that adopting MB algorithm ensures enhanced performance when compared to decoding the video without remapping. Also, the results demonstrate that adopting ALTD rather than APTD leads to additional performance enhancement.

D. Discussion and Comparison

In order to determine the relevancy of the devised algorithm, it is compared to the STM method introduced in [START_REF] Quan | A hybrid task mapping algorithm for heterogeneous MPSoCs[END_REF]. To achieve fair comparison, the STM method has been modeled and implemented on our devised NoC-based architecture. We have also implemented the exact method presented in [START_REF] Huang | A scalable and adaptable ILP-Based approach for task mapping on MPSoC considering load balance and communication optimization[END_REF] for the initial mapping, with two differences: we have used constraint programming instead of ILP, and the objective function is the maximum period, Eqn. 12, as it is our optimization goal. The workload used for the computation time of the actors is based on the profiling of Foreman video. Simulations have been conducted while running the MPEG4 decoder to process real-life videos.

1) Performance enhancement of MB remapping: The results presented in Fig. 18 show that for Foreman video sequence with CIF format (Fig. 18(a)), the use of MB remapping algorithm when adopting ALTD leads to a maximum performance enhancement of 38.2% (frame 280) and adopting MB-APTD leads to a maximum performance enhancement of 14.8% (frame 210) when compared to the results of processing the video without remapping. For Ice video sequence with 4CIF format (Fig. 18(b)), maximum performance enhancement of 56% (frame 450) and 16.5% (frame 250) are recorded when applying the MB algorithm adopting ALTD and APTD respectively. Furthermore, the use of MB algorithm adopting ALTD and APTD leads to a maximum performance enhancement of 10.92% (frame 120) and 7.6% (frame 50) for Bus video sequence with QCIF format (Fig. 18(c)) and Bus video with CIF format (Fig. 18(d)). For Grandma video with QCIF format (Fig. 18 [START_REF]in Signal, Telecom, Image, and Speech from the Lebanese University in 2007[END_REF] using MB remapping algorithm estimation of ALTD is more accurate and usually leads to better performance compared to APTD. However, in some cases APTD performs better such as for some observation windows of Grandma video (Fig. 18(e)). This refers to the fact that the heuristic is data-dependent and the link level prediction depends on the monitoring information collected during the previous data which may not match with the that of the current processed data.

2) MB remapping in comparison to STM remapping: Fig. 18 shows a comparison between our proposed remapping and the STM algorithm in terms of throughput (FPS). The results shows that the MB remapping outperforms STM remapping technique when considering either APTD or ALTD for estimating the NoC communication time delay.

Besides, the graphs in Fig. 18 show that in some cases the STM method leads to deterioration in the performance. In fact, the STM method selects critical task to be moved in each observation window without estimating the resulting total performance gain. Moving the task without determining its effects on the whole system performance degrades the overall performance. While in our proposed algorithm, the maximum achieved total gain among all mapping combinations is first determined as explained in subsection IV-E2c. Accordingly, a task is specified to be moved if the estimated maximum total gain is positive. It is noticed that in some observation windows no tasks are moved when the proposed algorithm is applied. A move is indicated by letter "M" in Fig. 18(a). In these cases, the estimation shows that no performance enhancement will be achieved for all mapping combinations.

3) MB remapping in comparison to optimal mapping: Fig. 18 also shows the results obtained from the mapping approach proposed in [START_REF] Huang | A scalable and adaptable ILP-Based approach for task mapping on MPSoC considering load balance and communication optimization[END_REF]. Note that the "optimal" mapping corresponds to the best mapping found based on the profiling of Foreman video after a time out of one hour (like the original paper), and the optimality is not proven. The results show that the MB algorithm, starting from a random mapping (without significant initial delay), performs better that the optimal with no remapping for Foreman video sequence in CIF format (Fig. 18(a)). As the optimality is searched for the Foreman profile, we used the optimal mapping as a starting point for the MB algorithm, and the results show that it further improves the throughput. As expected, the optimal mapping for Foreman does not perform good for the Ice video sequence in 4CIF format (Fig. 18(b)) and Grandma video sequence in QCIF format (Fig. 18(e)). But surprisingly, it performs good for the Bus video in QCIF format (Fig. 18(c)) and Bus video in CIF format (Fig. 18(d)). The so-called optimal method cannot be used for two reasons. First it introduces an unpractical initialization delay without guaranty of optimality. Secondly, a static solution is not appropriate to data-dependent applications since a solution can be good for one data-stream and inefficient for another one and more importantly the efficiency of a mapping varies over time. niques. The table shows that the MB algorithm achieves the maximum average performance enhancements of 26% and 14.11% when adopting ALTD and APTD respectively compared to the achieved throughput of processing the frames without remapping. Whereas, remapping using STM algorithm achieves a maximum average enhancement of 4%.

4) Comparison summary:

E. Scalability and generality

The scalability of our approach relies first on a negligible extra payload in the context of actor-level dataflow models, which intrinsically require a large amount of small control packets. For example, when decoding the Foreman video sequence the extra flits imposed by remapping (including the flits holding the binary codes of moved actors) constitute less than 0.02% of the flits used for dataflow. The proposed remapping method enhances the performance by exploiting the NoC structure and the characteristics of the available resources. The results show that our method positively impacts the NoC performance. Table VII illustrates the reduction percentages of packet hops when decoding different video sequences adopting the proposed MB remapping compared to ordinary decoding without remapping. The comparison shows that the proposed remapping method reduces the packet hops. The percentage of reduction is more than 20%. Secondly, the method includes the migration cost and so limits the number of moves. Fig. 19 shows the results obtained for a 4 × 6 NoC, for Foreman and Bus video sequences, starting from a random mapping. The results show that our approach can also improve the throughout for a larger NoC. On average, the throughout is improved by 13.5% and 4% for Bus QCIF and Foreman CIF videos respectively.

VI. CONCLUSION

This paper presents an original Move-based algorithm and NoC-based architecture to map the tasks of dataflow application during run-time. The method monitors the performance and intercommunication, takes the proper mapping decision and applies the required mapping configurations. The algorithm and the devised architecture are thoroughly presented. The best way to verify the effectiveness of a run-time mapping, which is by definition data dependent, is to simultaneously execute the target application. However such demonstrations are complex, time consuming and so ignored in the literature. In this paper we address this issue by conducting a SystemC simulation of the MPEG4-SP decoder with several real-life video sequences. The obtained results demonstrate that the proposed algorithm significantly enhances the performance. In addition, the proposed algorithm outperforms the available run-time mapping technique. Future work will consider the implementation of integrated module in the NIs and estimating the overhead in terms of area and energy.

Fig. 1 .

 1 Fig.1. Actors and software FIFO Models[START_REF] Martin | Notifying memories: a case-study on data-flow applications with NoC interfaces implementation[END_REF]

Fig. 2 .

 2 Fig. 2. The structure of the used NoC-based architecture

Fig. 3 .

 3 Fig. 3. Packets structure for mapping (left) and monitoring (right) information

Fig. 6 .Fig. 7 .

 67 Fig. 6. Manager command requesting the transfer of the moved actor code

( 1 )

 1 the communication time of each actor: T cm [A c ], (2) the computation time of each actor: T cp [A c ], (3) the number of input tokens corresponding to every input port of all actors: N T a total [A c [I j ] ], (4) the number of incoming tokens to each processor module from each memory module m: N T n total [S m , p], (5) the average communication delay of received tokens to each processor p from each memory module m: T av [S m , p], (6) the number of incoming tokens to each memory module m from each processor module p: N T n total [S p , m], and (7) the average communication delay of received tokens to each memory module m from each processor module p: T av [S p , m] where c ∈ {1, ..., |A|}, j ∈ {1, ..., |I c |}, m ∈ {1, ..., |M|} and p ∈ {1, ..., |P|}.

Fig. 8 .

 8 Fig. 8. Example on path declaration in the NoC

  ) The average communication-time delay per token T av [l] for each link l is determined by dividing the accumulated communication-time delay D total [l] by the number of tokens Algorithm 2 Average-link token delay (ALTD) Step 1: for each path P [Si,n] do a-Find the total communication-time delay D P total [S i , n] b-Calculate average communication time delay per link D L av [S i , n] end for Step 2: for each link l do a-Find the total link communication-time delay D total [l] b-Find the total number of tokens N T total [l] b-Calculate the average communication time delay per token T av [l] end for N T total [l] passing through this link.

  e p [C Ac,p ]. The new period of processor p is estimated by adding to the processor period P eriod p the estimated communication time T e cm [C Ac,p ] and the estimated computation time T e cp [C Ac,p ] of the moved actor A c as shown in the following expression: P eriod e p [C Ac,p ] = P eriod p + T e cp [C Ac,p ] + T e cm [C Ac,p ]

  Fig. 10 demonstrates an example of finding P eriod e max [C Ac,p ]. The figure considers the example illustrated in Fig. 9. Three actors are mapped to the looser processor P E 1 . The candidate list C includes three actors: A 1 , A 2 and A 3 . Six mapping combinations are illustrated: C A1,P E2 , C A1,P E3 , C A2,P E2 , C A2,P E3 , C A3,P E2 and C A3,P E3 . The figure shows how to find the maximum estimated period P eriod e max [C Ac,p ] for each mapping combination. It is shown in the figure that both the estimated communication time and estimated computation time of the same actor differ when mapped to different PEs.

  e per [C Ac,p ] and the estimated migration cost of the actor Cost e mig [C Ac,p ]. Gain e total [C Ac,p ] = Gain e per [C Ac,p ] -Cost e mig [C Ac,p ] (24)

4 .

 4 The complexity of each step is illustrated to determine the overall complexity. The complexity of Step1, the step of finding the period of each processor, is O(|P|). Then, Step2, the step of finding the processor with maximum period has the complexity of O(|P|). The complexity of Step3, estimating the total gains corresponding the move of the candidate actors to all PEs rather than the looser processor, is O((|P| -1).|A c ∈ C|). The complexity of Step4, choosing the best move, is O(|A c ∈ C|.(|P| -1)). If we consider a well balanced distribution of actors among the processors at initiation (|A c ∈ C| ≈ |A| |P| ), the overall complexity becomes O(|P|) + O(|A|) knowing that |P|-1 |P| ≈ 1.

Fig. 13 .Fig. 14 .

 1314 Fig. 13. Classification of control flits according to their types

Fig. 15 .

 15 Fig.[START_REF] Li | Chordmap: Automated mapping of streaming applications onto CGRA[END_REF]. Sum of packet time-delays (top) and average packet time-delay (bottom) while decoding Foreman video with CIF format[START_REF]in Signal, Telecom, Image, and Speech from the Lebanese University in 2007[END_REF]

Fig. 16 .Fig. 17 .

 1617 Fig.[START_REF] Huff | Clockwork: Resource-efficient static scheduling for multi-rate image processing applications on FPGAs[END_REF]. Total communication and computational times recorded throughout the observing windows during the decoding of the Foreman video with CIF format[START_REF]in Signal, Telecom, Image, and Speech from the Lebanese University in 2007[END_REF]; when adopting (a) ordinary decoding and (b) MB remapping

Fig. 18 .Fig. 19 .

 1819 Fig.[START_REF] Singh | Mapping on multi/many-core systems: Survey of current and emerging trends[END_REF]. Throughput in terms of FPS when decoding video sequences[START_REF]in Signal, Telecom, Image, and Speech from the Lebanese University in 2007[END_REF] using MB and STM remapping algorithms

TABLE I HARDWARE

 I

	ACCELERATORS USED IN THE SIMULATION PLATFORM
	PE ID	Accelerated Function Acceleration Ratio
	PE3 & PE6	IDCT	1/0.3
	PE4	IQ + IAP	1/0.75
	PE10	Add	1/0.57
	PE11	Interpolation	1/0.4

  Fig. 5. The structure of the packets holding the reading requests has to request the reading and/or writing indexes of input and output FIFOs. When the PE receives the value of demanded reading/writing index, it will check the satisfaction of the

	Packet header	origin / destination / type / time
	Packet payload	FIFO Address	Reading Order
	Packet header	origin / destination / type / time
	Packet payload		Reading Order FIFO Address
	Packet header	origin / destination / type / time
	Packet payload	FIFO Address	Reading Order New Index Value
	Fig. 4. Packet structures for holding reading (top) / writing (middle) index
	requests and set index (bottom)
	Packet header	origin / destination / type / time
	Packet payload	FIFO Address Reading Address	Data Size

firing rule. After reading/writing data from/to a FIFO, the reading/writing index has to be incremented by the size of the transferred data. The PE, which consumes/produces data, has to set the new reading/writing index in the targeted FIFO after reading/writing operation is performed. Accordingly, four types of packets are utilized: (1) Request read index, (2) Request write index, (3) Setting read/write index, and

TABLE IV PARAMETERS

 IV AND VARIABLES USED FOR THE MAPPING ALGORITHM

	Parameter Definition
		DPN application graph (DPNapp)
	|A|	Number (Nb) of actors
	|F|	Nb of FIFO channels
	|K|	Nb of data packets
	|Ic|	Nb of input ports of actor Ac
		Architecture graph (arch)
	|P|	Nb of processing elements
	|M|	Nb of memory modules
		Profiling data (profile)
	R i	Mean number of firings of actor i
	W i	Total computation cost of actor i
	Cs i	Instruction code size of actor i

  𝑃𝐸 2 𝑇 𝑐𝑝[𝐴 4 ] 𝑇 𝑐𝑚[𝐴 4 ] 𝑇 𝑐𝑝 [𝐴 5 ] 𝑇 𝑐𝑚[𝐴 5 ]

	𝑃𝐸 3 𝑇 𝑐𝑝 [𝐴 6 ] 𝑇 𝑐𝑚 [𝐴 6 ]
							𝑇 𝑐𝑝 𝑒 [𝐶 𝐴1,𝑃𝐸3 ]	𝑇 𝑐𝑚 𝑒 [𝐶 𝐴1,𝑃𝐸3 ]
	𝑃𝐸 1	𝑇 𝑐𝑝 [𝐴 2 ]	𝑇 𝑐𝑚 [𝐴 2 ]		𝑇 𝑐𝑝 [𝐴 3 ]	𝑇 𝑐𝑚 [𝐴 3 ]	𝑡𝑖𝑚𝑒
						𝑃𝑒𝑟𝑖𝑜𝑑 𝑚𝑎𝑥 𝑒	[𝐶 𝐴 1 ,𝑃𝐸 2 ]
	𝑃𝐸 3 𝑇 𝑐𝑝 [𝐴 6 ] 𝑇 𝑐𝑚 [𝐴 6 ]	𝑇 𝑐𝑝 𝑒 [𝐶 𝐴1,𝑃𝐸3 ] 𝑇 𝑐𝑚 𝑒 [𝐶 𝐴1,𝑃𝐸3 ]
	𝑃𝐸 2 𝑇 𝑐𝑝 [𝐴 4 ] 𝑇 𝑐𝑚 [𝐴 4 ] 𝑇 𝑐𝑝 [𝐴 5 ] 𝑇 𝑐𝑚 [𝐴 5 ]
	𝑃𝐸 1	𝑇 𝑐𝑝 [𝐴 2 ]	𝑇 𝑐𝑚 [𝐴 2 ]		𝑇 𝑐𝑝 [𝐴 3 ]	𝑇 𝑐𝑚 [𝐴 3 ]	𝑡𝑖𝑚𝑒
			𝑃𝑒𝑟𝑖𝑜𝑑 𝑚𝑎𝑥 𝑒	[𝐶 𝐴 1 ,𝑃𝐸 3 ]
	𝑃𝐸 3 𝑇 𝑐𝑝 [𝐴 6 ] 𝑇 𝑐𝑚 [𝐴 6 ]
	𝑃𝐸 2 𝑇 𝑐𝑝 [𝐴 4 ] 𝑇 𝑐𝑚 [𝐴 4 ] 𝑇 𝑐𝑝 [𝐴 5 ] 𝑇 𝑐𝑚 [𝐴 5 ]	𝑇 𝑐𝑝 𝑒 [𝐶 𝐴2,𝑃𝐸2 ]	𝑇 𝑐𝑚 𝑒 [𝐶 𝐴2,𝑃𝐸2 ]
	𝑃𝐸 1 𝑇 𝑐𝑝 [𝐴 1 ] 𝑇 𝑐𝑚 [𝐴 1 ]	𝑇 𝑐𝑝 [𝐴 3 ]	𝑇 𝑐𝑚 [𝐴 3 ]
					𝑃𝑒𝑟𝑖𝑜𝑑 𝑚𝑎𝑥 𝑒	[𝐶 𝐴 2 ,𝑃𝐸 2 ]
	𝑃𝐸 3 𝑇 𝑐𝑝 [𝐴 6 ] 𝑇 𝑐𝑚 [𝐴 6 ]	𝑇 𝑐𝑝 𝑒 [𝐶 𝐴2,𝑃𝐸3 ]	𝑇 𝑐𝑚 𝑒 [𝐶 𝐴2,𝑃𝐸3 ]
	𝑃𝐸 2 𝑇 𝑐𝑝 [𝐴 4 ] 𝑇 𝑐𝑚 [𝐴 4 ] 𝑇 𝑐𝑝 [𝐴 5 ] 𝑇 𝑐𝑚 [𝐴 5 ]
	𝑃𝐸 1 𝑇 𝑐𝑝 [𝐴 1 ] 𝑇 𝑐𝑚 [𝐴 1 ]	𝑇 𝑐𝑝 [𝐴 3 ]	𝑇 𝑐𝑚 [𝐴 3 ]	𝑡𝑖𝑚𝑒
			𝑃𝑒𝑟𝑖𝑜𝑑 𝑚𝑎𝑥 𝑒	[𝐶 𝐴 2 ,𝑃𝐸 3 ]
	𝑃𝐸 3 𝑇 𝑐𝑝 [𝐴 6 ] 𝑇 𝑐𝑚 [𝐴 6 ]
	𝑃𝐸 2 𝑇 𝑐𝑝 [𝐴 4 ] 𝑇 𝑐𝑚 [𝐴 4 ] 𝑇 𝑐𝑝 [𝐴 5 ] 𝑇 𝑐𝑚 [𝐴 5 ]	𝑇 𝑐𝑝 𝑒 [𝐶 𝐴3,𝑃𝐸2 ] 𝑇 𝑐𝑚 𝑒 [𝐶 𝐴3,𝑃𝐸2 ]
	𝑃𝐸 1 𝑇 𝑐𝑝 [𝐴 1 ] 𝑇 𝑐𝑚 [𝐴 1 ] 𝑇 𝑐𝑝 [𝐴 2 ] 𝑇 𝑐𝑚 [𝐴 2 ]	𝑡𝑖𝑚𝑒
				𝑃𝑒𝑟𝑖𝑜𝑑 𝑚𝑎𝑥 𝑒	[𝐶 𝐴 3 ,𝑃𝐸 2 ]
	𝑃𝐸 3 𝑇 𝑐𝑝 [𝐴 6 ] 𝑇 𝑐𝑚 [𝐴 6 ] 𝑇 𝑐𝑝 𝑒 [𝐶 𝐴3,𝑃𝐸3 ] 𝑇 𝑐𝑚 𝑒 [𝐶 𝐴3,𝑃𝐸3 ]
	𝑃𝐸 2 𝑇 𝑐𝑝 [𝐴 4 ] 𝑇 𝑐𝑚 [𝐴 4 ] 𝑇 𝑐𝑝 [𝐴 5 ] 𝑇 𝑐𝑚 [𝐴 5 ]
	𝑃𝐸 1 𝑇 𝑐𝑝 [𝐴 1 ] 𝑇 𝑐𝑚 [𝐴 1 ] 𝑇 𝑐𝑝 [𝐴 2 ] 𝑇 𝑐𝑚 [𝐴 2 ]	𝑡𝑖𝑚𝑒
			𝑃𝑒𝑟𝑖𝑜𝑑 𝑚𝑎𝑥 𝑒	[𝐶 𝐴 3 ,𝑃𝐸 3 ]

TABLE V PERCENTAGE

 V OF FLITS TRANSPORTED IN BCP FROM TOTAL FLITS

	Video		Remapping Algorithm
	Sequence Format	MB-ALTD	MB-APTD
	Foreman	CIF	0.0044%	0.0067%
	Bus	CIF	0.0008%	0.0125%
	Ice	4CIF	0.0027%	0.0019%
	Bus	QCIF	0.0348%	0.0272%

  Table VI summarizes the comparison of average FPS achieved when processing multitude video sequencing while adopting different remapping tech-

TABLE VI ACHIEVED

 VI RESULTS ADOPTING DIFFERENT REMAPPING TECHNIQUES

	Video		Remapping Algorithm
	Sequence Format	MB-ALTD MB-APTD	STM
	Foreman	CIF	11.4%	5%	4.1%
	Bus	CIF	5.4%	5.4%	-17.7%
	Ice	4CIF	26.1%	2%	-13.04%
	Bus	QCIF	9%	8%	-20%
	Grandma	QCIF	14.91%	14.11%	NA

  VII OF PACKET WITH MB-ALTD MB-APTD

	Video		Remapping Algorithm
	Sequence Format	MB-ALTD MB-APTD
	Foreman	CIF	20.94%	12.64%
	Bus	QCIF	3.24%	5.29%
	Grandma	QCIF	14.18%	8.33%