M D Galanis
email: mgalanis@ee.upatras.gr

A Milidonis

G Theodoridis

D Soudris

C E Goutis

A Partitioning Methodology for Accelerating Applications in Hybrid Reconfigurable Platforms *

In this paper, we propose a methodology for partitioning and mapping computational intensive applications in reconfigurable hardware blocks of different granularity. A generic hybrid reconfigurable architecture is considered so as the methodology can be applicable to a large number of heterogeneous reconfigurable platforms. The methodology mainly consists of two stages, the analysis and the mapping of the application onto fine and coarse-grain hardware resources. A prototype framework consisting of analysis, partitioning and mapping tools has been also developed. For the coarse-grain reconfigurable hardware, we use our previous-developed high-performance coarse-grain datapath. In this work, the methodology is validated using two real-world applications, an OFDM transmitter and a JPEG encoder. In the case of the OFDM transmitter, a maximum clock cycles decrease of 82% relative to the ones in an all fine-grain mapping solution is achieved. The corresponding performance improvement for the JPEG is 43%.

Introduction

Reconfigurable architectures have been a topic of intensive research activities in the past years. Reconfigurable fabrics are able to unify the performance of ASICs and the flexibility offered by the microprocessors [START_REF] Hartenstein | A Decade of Reconfigurable Computing: A Visionary Retrospective[END_REF]. In particular, hybrid (mixed) granularity reconfigurable systems [START_REF] Hartenstein | A Decade of Reconfigurable Computing: A Visionary Retrospective[END_REF]- [START_REF] Havinga | Energy Management for Dynamically Reconfigurable Heterogeneous Mobile Systems[END_REF] offer extra advantages in terms of performance and great flexibility to implement efficiently computational intensive applications (like DSP and multimedia) characterized by mixed functionality (data and control). Such hybrid architectures usually consist of: finegrain reconfigurable units usually implemented in FPGA technology, coarse-grain reconfigurable units implemented in ASIC technology, data and program memories, reconfigurable interconnection network, and microprocessor(s). Due to the special characteristics of the heterogeneous (coarse and fine-grain) reconfigurable units included in a hybrid platform, certain parts of the application are better suited to be executed on the coarsegrain units and other parts on the fine-grain units.

The fine-grain reconfigurable hardware's granularity usually ranges from 1 to 2-bits and it is realized by an embedded FPGA unit. Small bit-width operations can be efficiently executed by fine-grain hardware, as the granularity of the CLBs of the embedded FPGA is typically one or two bits. Tasks of Finite State Machine (FSM) type of functionality (i.e. control structures) are also good candidates to be implemented by the fine-grain reconfigurable hardware. The coarse-grain reconfigurable blocks are implemented in ASIC technology and execute the word-level or sub word-level operations. These blocks can slightly modify their functionality according to the application requirements.

It is widely adopted that the execution of word-level operations by coarse-grain units offers great advantages in terms of delay, area and reconfiguration time compared to the execution of these operations by the fine-grain reconfigurable units [START_REF] Hartenstein | A Decade of Reconfigurable Computing: A Visionary Retrospective[END_REF]. So, to exploit these advantages, the development of a methodology for partitioning an application in two parts, where the one is executed in the coarse-grain reconfigurable hardware and the other one in the fine-grain one, and mapping efficiently these parts on the corresponding reconfigurable units, is required.

In this paper, a formalized and automated partitioning methodology is presented for hybrid reconfigurable systems. The methodology is parameterized with respect to the reconfigurable hardware, i.e. the fine and the coarsegrain parts of the target architecture. It is assumed that both types of reconfigurable hardware are characterized in terms of timing and area characteristics. The introduced methodology was developed for the purposes of a European IST project, called Architectures and Methodologies for Dynamic REconfigurable Logic (AMDREL) [START_REF]Architectures and Methodologies for Dynamic REconfigurable Logic (AMDREL) project[END_REF]. The project's consortium is composed by industrial and academic partners.

The main contributions of the methodology are the analysis procedure at the basic block level of the application and the mapping procedures to the fine and coarse-grain hardware. A prototype software framework has been developed for implementing the proposed methodology. The methodology is evaluated in this paper using two real-world applications, an IEEE 802.11a OFDM transmitter and a JPEG encoder, both developed by the industrial partners of the AMDREL project [START_REF]Architectures and Methodologies for Dynamic REconfigurable Logic (AMDREL) project[END_REF]. The work presented here is an extension of our previous work [START_REF] Galanis | Mapping DSP Applications to a High-Performance Reconfigurable Coarse-Grain Data-Path[END_REF], where we developed a high-performance coarse-grain datapath and a methodology for mapping applications onto it.

The considered generic reconfigurable platform, which mainly targets the DSP and multimedia domains, is shown in Figure 1. The platform includes coarse and fine-grain reconfigurable hardware units for data processing, shared data memory, and a reconfigurable interconnection network. All the above components are typically integrated in a System-on-Chip (SoC) configured by microprocessor(s). This generic architecture can model a variety of existing hybrid (mixed) reconfigurable architectures, like the ones presented in [START_REF] Wan | Design methodology of a low-energy reconfigurable single-chip DSP system[END_REF], [START_REF] Havinga | Energy Management for Dynamically Reconfigurable Heterogeneous Mobile Systems[END_REF]. The paper is organized as follows: The related work is presented in section 2, while section 3 describes the proposed partitioning methodology. Experimental results are given in section 4. Finally, section 5 concludes this paper and presents future activities.

Related work

There has been considerable research for developing reconfigurable architectures in the past [START_REF] Hartenstein | A Decade of Reconfigurable Computing: A Visionary Retrospective[END_REF]. We are focusing on hybrid granularity platforms containing fine and coarsegrain reconfigurable hardware blocks.

The Pleiades [START_REF] Wan | Design methodology of a low-energy reconfigurable single-chip DSP system[END_REF] architecture is an approach that combines an on-chip microprocessor with a number of heterogeneous reconfigurable units of different granularities connected via a reconfigurable interconnection network. The Strategically Programmable System (SPS) [START_REF] Kastner | Instruction Generation for Hybrid Reconfigurable Systems[END_REF] is a hybrid reconfigurable system architecture that combines fine-grain reconfigurable units and ASIC coarse-grain modules which are pre-placed within a fully reconfigurable fabric. Chameleon project [START_REF] Havinga | Energy Management for Dynamically Reconfigurable Heterogeneous Mobile Systems[END_REF] considers a hybrid reconfigurable platform that contains microprocessor(s), an FPGA unit and coarse-grain reconfigurable units, called Field Programmable Function Arrays (FPFAs).

In the aforementioned hybrid reconfigurable systems, there is no a formalized partitioning methodology between the fine and coarse-grain reconfigurable units. In [START_REF] Havinga | Energy Management for Dynamically Reconfigurable Heterogeneous Mobile Systems[END_REF], a rather empirical manner is followed, which assigns bit-level parts of an application to the FPGA.

There has been also work in hardware-software partitioning of applications for reconfigurable architectures consisting of one RISC-type microprocessor and FPGA(s) [START_REF] Callahan | The Garp Architecture and C Compiler[END_REF], [START_REF] Ye | A C Compiler for a Processor with a Reconfigurable Functional Unit[END_REF]. However, those works do not consider coarse-grain reconfigurable blocks, thus they can not benefit from the computational ability of these units [START_REF] Kastner | Instruction Generation for Hybrid Reconfigurable Systems[END_REF], [START_REF] Wan | Design methodology of a low-energy reconfigurable single-chip DSP system[END_REF], [START_REF] Havinga | Energy Management for Dynamically Reconfigurable Heterogeneous Mobile Systems[END_REF].

Partitioning methodology

Research activities [START_REF] Suresh | Profiling tools for Hardware/Software Partitioning of Embedded Applications[END_REF] have shown that basic blocks inside loop structures represent a significant portion of the execution time for DSP and multimedia applications. The term basic block expresses a sequence of instructions (operations) with no branches into or out of the middle. At the end of each basic block there is a branch that controls which basic block executes next. The proposed partitioning methodology focuses on finding the most critical basic blocks (called kernels) of the input application. These kernels are executed on the coarse-grain hardware, so that the total execution time of the application meets the specification's requirements. With the term critical, we define the basic blocks that represent computationally intensive parts of the application. The critical basic blocks are often located in nested loops.

We are interested in exploiting the available parallelism at the operation level (either in critical or in non-critical parts of an application) in both types of reconfigurable hardware. Therefore, the methodology supports mutually exclusive execution of the fine and the coarse-grain hardware. According to their original C/C++ specification, critical and non-critical parts of the application are executed purely sequentially in the coarse and the fine-grain part of the architecture, respectively. Although, the methodology supports the mutual exclusive operation, this does not imply that either the fine or the coarse-grain hardware remain unused during the execution of the application. This is due to the fact that our generic hybrid reconfigurable architecture targets DSP and multimedia applications. Typically these applications process certain amount of data (called frames) whose computation is repeated over time. Through the pipelining among the stages of computations, the reconfigurable processing units of the hybrid architecture are always utilized.

In the following, we explain the proposed partitioning methodology. In Figure 2, the flow of the proposed methodology is shown. The input is the application (or a part of the application) which is described in a high-level language like C/C++. The application's source code is considered as the output of a hardware/software partitioning stage, which defines the parts that they are going to be executed in the reconfigurable hardware.

In the first step, the Control Data Flow Graph (CDFG) representation is created from the source code. This model of computation is extensively used in mapping applications on reconfigurable hardware. The CDFG is the input in the steps of mapping to fine and coarse-grain hardware and in the partitioning engine. In step 2, the application is mapped to the fine-grain hardware and the execution time is calculated. If the overall execution time of the application meets the timing constraints, then the methodology exits, since there is no need to continue with the next steps, i.e. to partition the application into fine and coarse-grain hardware. If the timing constraints are not satisfied, then we proceed to step 3, which is the analysis procedure. In the analysis procedure (step 3), the application's source code is processed, so as to identify the dominant kernels, which are the candidates to be mapped to the coarse-grain hardware. The rest of the application code is mapped to the fine-grain part of the architecture. The identification of kernels is a combination of dynamic and static analysis. The kernels are ordered in decreasing order of computational complexity.

In the partitioning engine (step 4), kernels are moved one by one for execution (and thus acceleration) in the coarse-grain hardware. After the movement of each kernel in the coarse-grain part, the total execution time of the application is calculated to check if the timing constraints are met. To compute the execution time, the mapping to the fine and coarse-grain hardware takes place. The time required for communicating data values through the shared data memory of Figure 1, between the two types of hardware is also taken into account.

The mapping to the coarse-grain part of the architecture is the step 5 of the proposed methodology. If there is still a violation in the overall execution time of the application, the procedures of moving kernels to the coarse-grain hardware and mapping the parts of the application onto the fine and coarse-grain parts, are repeated until the timing constraints are satisfied. As the mapping procedures to both types of reconfigurable hardware determine the execution time, we have developed appropriate algorithms to perform these procedures.

Analysis step

The analysis step is the procedure for identifying the kernels of the input application and provides the input to the partitioning engine block, as it is shown in Figure 2. More specifically, it identifies the critical and non-critical parts of the application. The critical part is the set of kernels, which are the basic blocks inside loops that cause performance overheads. These kernels are candidates to be mapped to the coarse-grain hardware, while the non-critical parts of the application are executed in the fine-grain hardware.

The inherent computational complexity (counts of basic operations and memory accesses) is a meaningful measure to identify dominant kernels. This information can be obtained through a combination of: (a) dynamic analysis (profiling), and (b) static analysis within basic blocks of the input specification. Since operations in a basic block do not have a uniform cost, a weighted sum is calculated and aggregated at the basic block level to indicate the computational complexity within the application. The weights indicate the delay allocated to each basic operator.

For the dynamic analysis, the source code is executed with appropriate input and profiling information is gathered at the basic block level. For performing dynamic analysis, we have used Lex [START_REF] Levine | [END_REF], which a lexical analyzer used for parsing the input code. By developing the proper scripts in Lex, we can identify loop (for, while and do-while) and conditionals (if-then-else) structures in the source code. Then, Lex automatically places a counter for each basic block in a loop. The modified source code (after counter placement) is compiled and executed with the input vectors that represent the typical operation of the application. The placed counter gives the access count for each basic block of the input program.

Lex is also used for the static analysis. It identifies the basic operations and the memory accesses inside the basic blocks and generates a detailed and illustrative overview of the distribution of the algorithm complexity over basic operators. The total weight (complexity) of a basic block is computed as the product of the basic block execution frequency (exec_freq) times the weight of the operations of this basic block (bb_weight), i.e.: _ _ _ total weight exec freq bb weight

(1) After all critical basic blocks have been identified, an ordering of these critical basic blocks takes place. These kernels are sorted in descending order of computational complexity. Thus, the first kernel which is going to be mapped onto the coarse-grain hardware, if the overall execution requirement is not met, is the most computational intensive one.

Mapping to fine-grain hardware

The proposed mapping methodology for the fine-grain part of the architecture is a temporal partitioning algorithm. The temporal partitioning resolves the hardware implementation of an application that does not fit into the fine-grain reconfigurable hardware by time-sharing the hardware in a way that each partition fits in the available resources (for example the CLBs of an FPGA). This timesharing of the hardware is achieved through the dynamic reconfiguration of the device, which is the case in contemporary FPGA devices, either commercial [START_REF]Xilinx Virtex-II Platform FPGAs[END_REF] or academic ones.

The mapping methodology classifies the nodes in the Data Flow Graph (DFG) of the input application according to their As Soon As Possible (ASAP) levels [START_REF] Micheli | Synthesis and Optimization of Digital Circuits[END_REF]. The ASAP levels expose the parallelism hidden in the DFG, i.e. all the DFG nodes with the same level can be considered for parallel execution without any dependency check. There also exists some degree of parallelism among the nodes with different levels, i.e. if they are not connected by a data edge. The approach followed is that the nodes are executed in increasing order relative to their ASAP levels. This ensures stable inputs for every DFG node at the next ASAP level. The mapping methodology also handles CDFG, by iteratively mapping the DFGs composing the CDFG.

The pseudocode of the proposed mapping algorithm to the fine-grain hardware is illustrated in Figure 3. Partition(u i ) denotes the temporal partition to which the node u i belongs (1 i u N , N is the number of DFG nodes) and max_level denotes the maximum ASAP level of any node in the DFG. The algorithm traverses each node of the DFG, level by level, and assigns them to a partition. The DFG nodes are assigned to partitions numbered 1 and beyond. All the nodes from level 1 to max_level are traversed. Nodes of the same ASAP level are placed in a single partition and if the available area in the fine-grain hardware is exhausted then the nodes are assigned to the next partition. If the nodes in the current ASAP level are all assigned to a partition, then the next level nodes are considered. Initially, a partition has no nodes.

The A FPGA is the area available for mapping the DFG operations in the fine-grain (FPGA) reconfigurable hardware. To ensure that the routing of the resources is feasible, the A FPGA is a percentage of the total FPGA area. A typical value is a 70% of the overall FPGA area. The size(u i ), which is the area occupied by the mapped DFG node, and the A FPGA are dependent from the fine-grain technology (e.g. a specific FPGA device [START_REF]Xilinx Virtex-II Platform FPGAs[END_REF]). Since these are parameters in our methodology, the proposed methodology is applicable to every type of reconfigurable fine-grain hardware. The shared data memory of the hybrid reconfigurable platform (Figure 1) is used for storing the input and output values among the temporal partitions. For each temporal segment a configuration bit-stream is generated. According to the application's data-and control-flow, the appropriate configuration bit-stream is loaded to the FPGA device. For each temporal partition, full reconfiguration of the finegrain hardware is performed. Thus, the reconfiguration time has the same value for each partition and it is added to the execution time of each temporal partition.

Mapping to coarse-grain hardware

For the coarse-grain hardware, the high-performance coarse-grain data-path and the mapping methodology presented in [START_REF] Galanis | Mapping DSP Applications to a High-Performance Reconfigurable Coarse-Grain Data-Path[END_REF] are considered. This data-path consists of a set of Coarse-Grain Components (CGCs) implemented in ASIC technology, a reconfigurable interconnection network, and a register bank. The CGC is an nxm array of nodes, where n is the number of rows and m the number of columns. The connections among the CGC nodes are reconfigured by appropriate steering logic. This allows to easily realize any complex operations (like a multiply-add operation) and increase system's performance [START_REF] Galanis | Mapping DSP Applications to a High-Performance Reconfigurable Coarse-Grain Data-Path[END_REF]. Each CGC node contains a multiplier and ALU where only one of them is activated in a clock cycle.

Due to the flexible structure of the CGC-based datapath, any required computational structure can be easily implemented; thus the CGC data-path can realize the behaviour of any existing coarse-grain data-path, like the ones in [START_REF] Kastner | Instruction Generation for Hybrid Reconfigurable Systems[END_REF], [START_REF] Wan | Design methodology of a low-energy reconfigurable single-chip DSP system[END_REF]. This is the main reason why we have considered in this work this specific type of coarse-grain hardware. Also, due to the CGC data-path's features, the stages of the mapping methodology are accommodated by simple, yet efficient algorithms. The steps of the mapping process are: (a) scheduling of DFG operations, and (b) binding with the CGCs. A proper list-based scheduler has been developed. After CGC binding [START_REF] Galanis | Mapping DSP Applications to a High-Performance Reconfigurable Coarse-Grain Data-Path[END_REF], the overall latency of the DFG is measured in clock cycles having period T CGC . This period is set for having unit execution delay for the CGCs. For handling CDFG, the mapping procedure is iterated through the DFGs comprising the CDFG of an application.

Partitioning engine

The partitioning engine moves kernels one by one to the coarse-grain hardware until the performance requirements are satisfied. After the movement of each kernel to the coarse-grain hardware, the total execution time of the application is calculated to check if the timing constraints are met. The mapping procedures to the fine and coarsegrain hardware are required for computing the execution time. If the timing constraints are not met, the process of moving kernels to the coarse-grain hardware is repeated until the timing constraints are satisfied. The total execution time is:

t total = t FPGA + t coarse +t comm (2)
where t FPGA is the execution time in the FPGA (fine-grain) hardware, t coarse is the execution time in the coarse-grain data-path and t comm is the time required for transferring data between the two types of reconfigurable hardware, through the shared data memory (Figure 1).

The The t FPGA includes the reconfiguration time for all the generated temporal partitions after the mapping of the basic blocks.

t

Experimental results

We have developed a prototype framework in C++ to implement the flow of Figure 2. For the software development, we have also used academic open source tools. For example, the SUIF2 [START_REF] Hall | Maximizing multiprocessor performance with the SUIF compiler[END_REF] and MachineSUIF [START_REF] Smith | An introduction to Machine SUIF and its portable libraries for analysis and optimization[END_REF] compiler infrastructures has been used and proper passes have been developed for the CDFG creation. As already mentioned, Lex has been used for the dynamic and static analysis.

In this paper, we apply the proposed partitioning methodology to two applications written in C language by the AMDREL's partners [START_REF]Architectures and Methodologies for Dynamic REconfigurable Logic (AMDREL) project[END_REF]. The first one is the front-end of the baseband processing of an IEEE 802.11a OFDM transmitter. The front-end consists of the Quadrature Amplitude Modulation (QAM) unit, the IFFT block and the cyclic prefix unit. The considered source code of the OFDM transmitter is composed by 18 basic blocks (BBs). The second application is a JPEG encoder. The main parts of the JPEG encoder are the DCT transformation unit, the quantizer, the zig-zag scanning unit and the entropy (Huffman) encoder. The considered JPEG encoder source code consists of 22 BBs.

Table 1 reports the total weights of both applications (last column), in decreasing order of value, of the 8 most computational intensive basic blocks, extracted by the analysis step of the partitioning methodology. The second column of this Table reports the execution frequency of the specific basic block, while the third column gives the weights of the operations in the basic block. The execution frequency values are taken for a number of 6 payload symbols for the OFDM transmitter, while for the JPEG encoder for transforming an image of size 256 256 bytes. These inputs of the applications also hold for the clock cycles results of Table 2 and3. The DFGs of the basic blocks of both applications consist of arithmetic operations of type ALU and multiplication; thus no divisions are present in the DFGs. In the analysis process, we give a weight equal to 1 for the ALU operations and a weight equal to 2 for the multiplication ones, since the later ones have a larger computational complexity. Table 2 and 3 show the results of the partitioning methodology, in terms of clock cycles, after using the developed partitioning framework for the OFDM transmitter and the JPEG encoder. The following assumptions hold for both applications. The clock cycle period is set to the clock period of the fine-grain (FPGA) hardware. We have considered that the clock cycle period of the FPGA hardware is three times larger than the CGC data-path's clock period, i.e. T FPGA = 3 T CGC . This is a rather moderate assumption for the performance gain of an ASIC technology compared to an FPGA one. For these experiments, two values of A FPGA are considered: 1500 and 5000 units of area. For each case of the A FPGA , the coarse-grain data-path consists of two and three 2x2 CGCs. Thus, four different cases are considered in this experiment. For all of these cases, a timing constraint of 60000 clock cycles has to be satisfied for the OFDM transmitter, while for the JPEG encoder a timing constraint of 11 10 6 clock cycles has to be met. The first row of Table 2 and 3 shows the number of cycles for an all-FPGA implementation of the considered applications. It is evident that an all-FPGA solution cannot satisfy the timing constraint. The third row of Table 2 and3 shows the clock cycles required for the implementation of the BBs (their number is shown in the fourth row of the Table 2 and3) when these are mapped to the CGC datapath. The number and type of CGCs are given in the second row. The BBs of the fourth row have been chosen from the partitioning methodology for execution on the coarse-grain.

The final clock cycles, after the partitioning, are shown in the fifth row of Table 2 and3. It is clear from these results, that by choosing costly BBs to be mapped in the coarse-grain reconfigurable hardware, system's performance is largely improved and the timing constraint is satisfied. These results prove the effectiveness of both the proposed partitioning methodology and the automated framework. Also, as the FPGA area grows, the reduction of clock cycles is smaller since a larger FPGA exploits better the parallelism of an application due to the considered finegrain mapping algorithm shown in Figure 3. A maximum clock cycles reduction of approximately 82% relative to the all-FPGA solution of the OFDM transmitter, is reported for the case of A FPGA =1500 and three 2x2 CGCs present in the CGC data-path.

Conclusions -Future work

A methodology for partitioning applications between fine and coarse-grain reconfigurable blocks of a hybrid granularity architecture, was presented. We also gave specific mapping algorithms for the fine and coarse-grain reconfigurable blocks. The experiments showed that the timing constraints of an application can be satisfied by proper functional partitioning. On going-work considers multiple threads of execution for parallel operation of the fine and coarse-grain reconfigurable blocks. Future work focuses on partitioning an application for satisfying energy consumption constraints.

Figure 1 .

 1 Figure 1. Generic reconfigurable platform architecture.

1 Figure 2 .

 12 Figure 2. Block diagram of the proposed partitioning methodology.

Mapping algorithm to fine-grain hardware.

	i = 1;
	level = 1;
	area_covered = 0;
	while(level max_level)
	for each node u i with level(u i )= level
	current_area = size(u i );
	if (area_covered + current_area	A FPGA )
	partition(u i ) = i;
	area_covered = area_covered + current_area;
	end if;
	else
	i = i + 1;
	partition(u i ) = i;
	area_covered = current_area;
	end else;
	level = level + 1;
	end for;
	end while;
	Figure 3.

  coarse equals to: where t to_coarse is the time required for executing the basic block BB i in the coarse-grain hardware, and Iter(BB i ) is the number of times that the BB i is invoked. Similarly, t FPGA equals to:

	t	coarse	t	_ to coarse	(	) B B I t e rB B ( i i	)	(3)
			i
	t	FPGA	_ to FPGA t	(	) BB Iter BB ( i i	)	(4)
			i

Table 1 . Ordered total weights of basic blocks Basic Block no.

 1

		Basic Block	Operations	Total
		exec. freq.	weight	weight
		OFDM transmitter
	22	336	115	38640
	12	1200	25	30000
	3	864	6	5184
	5	370	12	4440
	42	800	5	4000
	32	560	6	3360
	29	448	7	3136
	21	147	18	2646
		JPEG encoder
	6	355024	3	1065072
	2	8192	85	696320
	1	8192	83	679936
	22	65536	5	327680
	8	30927	8	247416
	3	65536	3	196608
	16	63540	3	190620
	17	63540	2	127080

Table 2 . OFDM partitioning results for timing constraint of 60000 clock cycles

 2

		A FPGA =1500	A FPGA =5000
	Initial Cycles	263408	124080
	CGCs no.	two 2x2	three 2x2	two 2x2	three 2x2
	Cycles in CGC	53184	41472	53184	41472
	BB no.	22, 12, 3	22, 12	22, 12, 3	22, 12
	Final cycles	57088	47856	56864	46512
	% cycles reduction	78.3	81.8	54.1	62.5

Table 3 . JPEG partitioning results for timing constraint of 11 10 6 clock cycles

 3

		A FPGA =1500	A FPGA =5000
	Initial Cycles ( 10 6 )	18434	12399
	CGCs no.	two 2x2	three 2x2	two 2x2	three 2x2
	Cycles in CGC ( 10 6 )	5817	5699	5817	5669
	BB no.	6, 2, 1	6, 2, 1	6, 2, 1	6, 2, 1
	Final cycles ( 10 6 )	10558	10411	10423	10227
	% cycles reduction	42.7	43.5	15.9	17.5

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

* This work is partially supported by the project IST-2001-34793-AMDREL funded by the E.C. Also, it was partially funded by the Alexander S. Onassis Public Benefit foundation.


F Masi

I Stefanou

P Vannucci
email: paolo.vannucci@uvsq.fr

On the origin of the cracks in the dome of the Pantheon in Rome

Keywords: monumental structures, Pantheon in Rome, Roman concrete, cracks

In this paper we aim at giving a contribution to a problem that has been the subject of previous studies since some decades: the reason and period of formation of the meridional cracks that affect the dome of the Pantheon of Rome. This problem is investigated using a detailed three-dimensional finite-element simulation in which material nonlinearities, as well as a plausible sequence of the construction stages, are modeled. In particular, we show that concrete shrinkage, together with gravity may have been the main mechanical causes of the cracks in the early phases of the building's life. Unlike previous studies on the matter, that have largely inspired our research and where simplified 2D finite element models of the Pantheon were used, we make use of a detailed 3D model of the Pantheon's structure, that takes into account for both the particular geometry of the building, and namely the presence in the dome of a coffering and of caveas, and of the differences in the materials. The nonlinear numerical simulations, in addition, aim at reproducing, through different steps, the (probable) true constructing sequence of the dome, in order to obtain numerical results as much as possible close to reality. The results of our simulations show a rather surprising correspondence with the actual state of the dome: in fact, the overall pattern of the cracks so found is in a very good agreement with the real one, for both the number of the cracks and their extent, which shows that concrete shrinkage may have been the true reason for the presence of the meridional cracks. We have also investigated the role of the stepped rings that exist in the outer part of the dome; we show in this case that some previous studies are not necessarily contradictory, but rather complementary.

D R A F T 1 Introduction 1.

The object of the study

The Pantheon is one of the most admired and studied monuments ever1 . The building that has come to us is actually the fourth Pantheon, built upon the rests of previous temples of classical rectangular form, by the Emperor Hadrian, since A.D. 118 to about 128, or later, perhaps until 140, under Emperor Antoninus Pius.

The Pantheon is probably the joint work of Hadrian and of the Nabatean great architect Apollodorus of Damascus, at least until 121, when seemingly he was first exiled by Hadrian and then executed in 125, according to Dione Cassius. Apollodorus was the architect of many great constructions during the reign of the Emperor Trajan, namely of the great bridge over the Danube, of the Trajan's Forum and Markets, of the artificial harbor of Porto and so on.

The main body of the Pantheon, the so-called Rotonda recalls, probably intentionally, the celebrated discovery of Archimedes of the volume of a sphere inscribed in a cylinder [START_REF] Boyer | A history of mathematics[END_REF]. In fact, see Figure 1, the Rotonda is composed by a cylinder whose inscribed sphere is coincident, for its upper part, with the dome, while its bottom touches the ground. The touch of Archimedes is present also with regard to another aspect: the coffering that is sculpted in the intrados of the dome is subdivided into 28 parts, and it was Archimedes that studied the related problem of partitioning a circle into 7 parts. The coffering, besides its aesthetic role, serves also to reduce the dome's weight. [START_REF] Pulvirenti | Didatticarte[END_REF]).

With a diameter of 43.30 m, according to the measurements of de Fine Licht [K. [START_REF] De Fine Licht | The Rotunda in Rome: a study of Hadrian's Pantheon[END_REF][START_REF] Mark | Light, wind and structure[END_REF], or 150 Roman feet, i.e., 44.55 m, according to Wilson-Jones D R A F T

Figure 2: Meridional cracks in the Rotonda's dome (after [START_REF] Terenzio | La restauration du Panthéon de Rome[END_REF]).

[ [START_REF] Wilson-Jones | Principles of Roman Architecture[END_REF], Como, 2013], the Pantheon's dome is, still today, the largest dome made of unreinforced concrete in the world 2 . This constructive technique, so characteristic of the Roman Empire period, was mastered by Apollodorus, who had already used it in different other buildings, e.g. the vault of the Great Hall in the Trajan's markets in Rome, see [Perucchio and[START_REF] Perucchio | Concrete vaulting in Imperial Rome: A structural analysis of the Great Hall of Trajan's Markets[END_REF][START_REF] Perucchio | The Evolution of Structural Design of Monumental Vaulting in Opus Caementicium in Imperial Rome[END_REF].

While the intrados is sculpted by a coffering, the external lowest part of the dome is formed by stepped rings, see Figure 1, whose function has been the object of different investigations, related also to the object of this study.

This concerns the presence and origin of cracks in the dome. Such cracks have an almost meridional direction and stop at a latitude of approximately 57 • , where the hoop stress begins to be compressive.

The distribution of these meridional cracks, as shown in Figure 2, was detailed in 1934 by A. Terenzio, the Superintendent of the Monuments of Latium, who had carried on a series of inspections on the dome of the Rotonda after the fall of some fragments [START_REF] Terenzio | La restauration du Panthéon de Rome[END_REF]. Terenzio inferred that the cracks appeared rather soon after the construction, by noticing that some bricks used for ancient cracks repairs were marked by the same stamps with those used for the original parts of the building.

Previous studies on the Pantheon's dome

In an early application of Finite Element Analysis (FEA) to Roman structures, Mark and Hutchinson [START_REF] Mark | Light, wind and structure[END_REF]Hutchinson, 1986, Mark, 1990] used a simplified two-dimensional model of the Rotonda, exploiting the axial symmetry of the structure. According to this study, and contrary to what commonly thought, the step-rings do not serve to reduce to an admissible value the hoop tension in the lowest part of the dome, due to the presence of the meridional cracks.

Mark and Hutchinson proposed different conjectures to explain the presence of the cracks: foundation settlements, shrinkage of concrete in the early phases, differential temperature 2 Actually, the Pantheon's dome is larger than the dome of Saint Peter in Vatican, diameter of which is 42 m, and also of the octogonal dome of F. Brunelleschi, in Santa Maria del Fiore at Florence, with base circumscribed by a circle of 41.57 m diameter. In addition, unlike Pantheon, these two famous domes, like many others, are made of bricks, not concrete.

D R A F T

on the dome. As far it concerns the presence of the step-rings, they gave two possible reasons. The first one is related to the construction technique: it is easier to build the lower part of the dome using the step-rings than a smooth extrados, too steep in this zone. The second, is structural: according to them, Romans probably expected, based on experience, the dome to be cracked since the beginning, which changes dramatically its static regime as the hoop stress cannot be transmitted anymore through the dome. Therefore, the whole behavior of the Rotonda is more similar to that of an array of wedgeshaped arches3 , and in this case, the use of the step-rings is substantial: their action is like that of an overload over the haunch of an arch. Using an iterative procedure, they showed that if tensile stresses are not permitted, cracks extend up to 54 • , value which is in agreement with the observed cracks of the dome. Finally, the basic idea of Mark and Hutchinson is that Romans knew that meridional cracks in unreinforced concrete domes were inevitable and present since the first period after the construction, which is proved by the construction of the step-rings.

Recently, the conclusions of Mark and Hutchinson have been criticized by Brune in his PhD thesis [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF]. Brune has used a FEA of the Rotonda similar to that of Mark and Hutchinson, i.e., using a two-dimensional model with imposed axi-symmetry. The conclusion drawn is exactly the opposite, and namely that the step-rings improve the hoop resistance of the dome leading to a reduction of the hoop stress with respect to the case without step-rings. As far it concerns the cracks, without firmly propounding a specific cause, Brune seems to indicate foundation settlements the most likely reason for the cracks and rises some doubts on the cracks origin time by arguing that the bricks used for repairs have been actually used in the exterior of the Rotonda. According to Brune, this shows that the dome cracks documented by Terenzio cannot be dated back with sufficient confidence to a period close to the construction of the monument. They could have appeared at that time, for instance in the form of micro-cracks which propagated further the cracks opening, over a long period, probably due to ground settlements and/or earthquakes.

Motivation of the present study

The analysis of Mark and Hutchinson, based on a 2D model, makes use of an iterative procedure to introduce the formation and propagation of the meridional cracks as consequence of a too high tensile hoop stress. However, in doing so, the axial symmetry is no more a valid assumption and, though they arrive to a rather correct value of the cracks extension, it is questionable wether or not their 2D model is really representative of the 3D problem. Actually, the conclusion of Brune, still based on a 2D model, is opposite to that of Mark and Hutchinson.

Morer and Goñi have proposed in 2008 a study based on a 3D detailed Finite Element (FE) model of the Rotonda, but without taking into account the coffering [START_REF] Morer | A benchmarking study of the analysis of non-reinforced structures applied to the structural behavior of domes. In Structural Analysis of Historic Construction: Preserving Safety and Significance[END_REF]. Their study seems not to be focused on the origin of the cracks, because such cracks are already part of their model and are used uniquely to assess the subsequent D R A F T stress distribution. Therefore, to the authors knowledge, an accurate 3D study oriented to determine the possible origin of the meridional cracks is still lacking.

The study we present is, in fact, a contribution to this technical and historical problem and it tries to give a possible explanation of the cracks origin through the simulation of the building phases. Namely, we investigate, including the early transient phase of concrete setting, whether or not concrete shrinkage could have been able to produce a crack pattern of the type observed by Terenzio. The study relies on numerical simulations with a detailed 3D FE model of the Rotonda, making use of a nonlinear constitutive law.

The results reveal a crack pattern which is in good accordance with the observed one. This allows us to presume that concrete shrinkage and gravity are likely to be the two main mechanical causes of the cracks and that these last may really be arisen in the early phases of the building's life. Of course, as for any inverse problem, it is difficult to exclude other factors and causes, such as ground settlements, so in the end our analysis clearly shows that the conjugate effect of concrete shrinkage and gravity is a sufficient condition for explaining the presence and the formation period of the observed meridional cracks.

Such a result is to be ascribed to the technology used by Romans for the construction of the Pantheon's dome: a structure in unreinforced concrete is, one one hand, submitted to the phenomenon of shrinkage and to gravity, on the other hand, like masonry or stone structures, unreinforced concrete can withstand only low tension stresses. The combined final effect is the appearance of cracks in the dome.

Finally we address the previously risen issue on the effect of the presence of the step-rings in the Rotonda's state of stress and we compare the results with those given in [START_REF] Mark | On the Structure of the Roman Pantheon[END_REF]] and [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF].

Modeling the material behavior

Pantheon is made by different materials and we have considered five different zones, corresponding to those indicated in Figure 3: foundation, brick-faced concrete of the cylindrical wall, lower, intermediate and upper zone of the dome. The columns are made of granite. Concerning the dome, it is composed of different aggregates, from the heaviest one in the lower part, with thickness ∼ 5.9 m, to the lightest one in the upper part of the dome, where the thickness decreases to ∼ 1.5 m.

The materials are assumed homogeneous and linearly elastic in compression. It is commonly considered that in monumental structures compression stresses are very low, usually an order of magnitude below the compressive strength of the material, cf. [START_REF] Heyman | The stone skeleton[END_REF][START_REF] Stefanou | Three dimensional homogenization of masonry structures with building blocks of finite strength: A closed form strength domain[END_REF], so that there is no possibility of crushing. The consistency of this modelling assumption is hence checked by monitoring that the compressive stresses do not exceed the compressive strength, assumed to be, for concrete, equal to ∼ 5 MPa, according to the experimental results by [START_REF] Samuelli-Ferretti | Materiali da costruzione e tecnologie costruttive del patrimonio archeologico e monumentale romano con particolare riferimento al tipo laziale ed all'opus latericium[END_REF] and [START_REF] Giavarini | Mechanical behaviour and properties[END_REF] and the models proposed in [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF] and [START_REF] Ivancic | A Concrete Damage Plasticity Model for Ancient Roman Pozzolanic Concrete[END_REF], and ∼ 123 MPa for granite, see [START_REF] Buyukozturk | Interface fracture and crack propagation in concrete composites[END_REF].

D R A F T

Figure 3: Materials composing the Rotonda as in [START_REF] Lancaster | Concrete Vaulted Construction in Imperial Rome[END_REF] (left) and in Table 1.

Under tension, a linear elastic behavior is assumed until the maximum principal stress reaches the tensile strength, f t . A subsequent tensile softening is considered in terms of the nonlinear brittle cracking model proposed in [START_REF] Hillerborg | Analysis of crack formation and crack growth in concrete by means of fracture mechanics and finite elements[END_REF], ABAQUS, 2016]. According to this law, when the maximum principal stress reaches f t , a fictitious crack is formed in the plane orthogonal to the direction of the principal tensile stress. We assume, for the sake of simplicity, that the orientation of the planar Mode I crack remains constant in the three-dimensional space. Once the peak tensile stress is reached, a linear softening branch is followed based on the fracture energy G f . This allows to minimize mesh dependency due to the softening behavior and to dissipate adequately the energy in the numerical simulations [ABAQUS, 2016].

For what concerns the choice of the mechanical characteristics of the materials, the densities have been fixed upon the indications given in [START_REF] Mark | On the Structure of the Roman Pantheon[END_REF], while the other properties have been derived upon the identification of a rationale link to the densities so that, starting from few known data, the other ones can be assessed. Indeed, according to historians and researchers in mechanics of ancient monuments, the physical properties of concretes and mortars of the past have different characteristics with respect to modern concrete. In particular, as already said, the Pantheon's dome has been realized by the Roman concrete, based on the use of the pozzolana, a pumice stone of volcanic origin, and of different aggregates, from ordinary gravel in the lower part to pumice aggregates in the upper part, so as to obtain a material whose density decreases from the bottom to the top of the dome.

Unfortunately, the data that can be found in the literature on Roman concrete are not systematic nor complete. However, experimental tests have shown that the tensile behavior of Roman concrete follows that of mortar (see [START_REF] Samuelli-Ferretti | Proposte per lo studio tecnico-sperimentale della statica dei monumenti in opus caementicum[END_REF][START_REF] Giavarini | Mechanical behaviour and properties[END_REF][START_REF] Jackson | Assessment of material characteristics of ancient concretes, Grande Aula, Markets of Trajan, Rome[END_REF]), due to a rather low contrast of the tensile strength between the Roman concrete's aggregates and the mortar itself [START_REF] Jackson | Assessment of material characteristics of ancient concretes, Grande Aula, Markets of Trajan, Rome[END_REF]. This gives a material which is less heterogeneous than modern concrete and which behaves more as a mortar, at least in the traction regime. Consequently, it is possible to model Roman concrete as an equivalent mortar, in the absence of more precise experimentally derived mechanical properties.

D R A F T

For all the concretes, we have assumed a Poisson's ratio ν = 0.2, as proposed in [Como, 2013]). The Young's moduli for concrete aggregates of the dome and the cylindrical part are derived from [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF] and [Como, 2013], respectively. Based on modern technical recommendations for lightweight concrete [START_REF] Sanpaolesi | Calcestruzzo leggero strutturale di argilla espansa[END_REF], relationships between the Young's modulus, tensile strength and density have been extrapolated. Concerning the fracture energy, we have used the linear relationship in [START_REF] Dehn | Fracture mechanical behaviour of lightweight aggregate concrete[END_REF]. For more details the reader is addressed to [START_REF] Masi | Blast actions from high explosives. Studies on their simulation and effects[END_REF] and [START_REF] Masi | A study on the effects of an explosion in the Pantheon of Rome[END_REF].

Regarding the concrete composing the dome, we have considered the material properties in [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF], where some typical values of different material parameters, and namely the Young's modulus, E, f t , and G f , as well as a bilinear approximation of the experimental softening curve, are reported for a reproduction of ancient Roman mortar as a function of the curing duration. Since we are dealing with the simulation of the shrinkage of concrete, the interesting values for the present analysis are those referring to 28 days.

Table 1 shows the material parameters for the different zones of the model.

Numerical simulations

The target of this study is the assessment of the role of initial shrinkage in the formation of the meridional cracks that spread across the dome. Concrete hardening is a complex thermo-hydro-mechanical process characterized by exothermic chemical reactions and internal drying that cause also volume change, especially in the early stages of curing, known as shrinkage. In the present analysis, only the mechanical effects of the process of shrinkage is considered by modeling it as an imposed volume change, ε v , produced by an equivalent change of temperature ∆T < 0:

ε v = α ∆T, ( 1
)
where α is the thermal expansion coefficient. In fact, the overall effects of concrete shrinkage and temperature change are the same: a change of volume. The numerical simulations performed simulating the shrinkage of the concrete by a decrement of the temperature are hence correct to represent the phenomenon, provided that the temperature decrease used in the numerical simulations is quantitatively correct.

Shrinkage depends on the amount of water used to mix the aggregates, curing time and ambient relative humidity, among other parameters, and for modern concrete amounts

D R A F T
to a volume change ε v = 0.15 ÷ 0.30 × 10 -3 . For the problem at hand, a parametric analysis at varying of the ratio ε v /α, thus of ∆T , seems to be a good choice to overcome the uncertainties of selecting, in the case of Roman concrete, realistic values for both the volumetric straining and the thermal expansion coefficient.

The procedure used for simulating the effects of initial shrinkage in concrete, occurred during the construction of the dome, requires a proper characterization of the casting process. To this purpose, the following hypotheses are made:

a. The dome was cast by pouring concrete over a wooden formwork [START_REF] Como | Large structures behaviour: the past and the future[END_REF], assumed to be self-supporting;

b. The frames are left in position to allow the structure to harden; we assume that, once the concrete has set, the formworks are left in place to let the concrete reach a sufficient strength. Shrinkage happens during this phase.

c. The formwork is finally removed, and the dome can freely deform under the action of its own weight.

The simulation is accordingly split in three different steps:

1. First, we apply the gravity to the structure, which is supported by formworks. The application of the load is done through an implicit static analysis.

2. The results obtained are then used as the initial state of a subsequent nonlinear explicit analysis in which the volume change due to shrinkage is simulated by an incrementally applied thermal load, ∆T . The load is applied slowly in order to minimize dynamic effects.

The presence of the self-supporting formwork is modeled by imposing a zero vertical displacement at the inner face of the dome.

3. A second explicit analysis finally models the progressive decentering of frames by removing the boundary condition corresponding to the self-supporting formwork progressively to ensure that no inertial effects take place, meaning that the kinetic energy of the system is neglectable (< 5%) with respect to strain energy, [ABAQUS, 2016]. The nonlinear simulations are done assuming a mass-proportional damping for the explicit analyses in order to reach equilibrium rapidly and dissipate undesirable inertial effects (quasi-static condition). We have used a FEM composed of 3.7 millions of deegres of freedom (DOF), made of four-nodes thermally coupled tetrahedral elements, see Figure 4. This choice has been done after a mesh convergence analysis, as explained in [START_REF] Masi | A study on the effects of an explosion in the Pantheon of Rome[END_REF].

We have simulated the shrinkage of the dome for different volumetric straining to thermal expansion coefficient ratios, starting from a (ε v /α) 1 = 3.4 K till (ε v /α) 5 = 4.55 K, which corresponds to the maximum value of ε v /α if a stable configuration has to be found for the dome, at the end of the simulations, through equally-spaced increments. For each ratio, we have monitored the average and maximum latitude reached by the meridional cracks above the springing, θ mean and θ max respectively, and the azimuthal frequency, i.e." the reciprocal of the average azimuthal angle between two consecutive cracks, f ϕ = 1/ϕ mean (see Fig. 5). Table 2 shows the results of the calculations and Figure 6 the relative crack patterns.

Table 2: Number of cracks, average and maximum latitude and azimuthal frequency. We can clearly notice a sort of invariance of the azimuthal frequency for ε v /α ≥ (ε v /α) 2 : fifteen meridional cracks spread the dome independently from the volumetric strain, thus from the amount of shrinkage. This value coincides almost perfectly with that reported by Terenzio of fourteen major cracks. This can be put into correspondence with the existence of fifteen equally-spaced caveas present at the base of the dome itself: all the major cracks stem from such caveas to propagate meridionally throughout the dome (see Fig. 7). The slight difference in the azimuthal frequency could, however, be explained if one considered the presence of the pronaos located at the entrance of the Pantheon (see Fig. 9), which, if constructed at the same time of the dome, could have prevented the formation of D R A F T

ε v /α N cracks θ mean θ max f ϕ [K] [ • ] [ • ] [ •-1 ] 1 3.
Figure 6: Crack patterns at the end of the calculations for the different volumetric straining to thermal expansion coefficient ratios, as defined in Table 2.

the fifteenth crack above the entrance door, by limiting the volumetric straining of the contiguous part of the dome. Indeed, looking at the pattern photographed by Terenzio (Fig. 2), we can notice a sort of symmetry to a plane passing from the extremities and the center of the figure itself. That is, with respect the plane of symmetry of the building. Moreover, the azimuthal distance between the first left-hand side and the last right-hand side cracks is higher with respect to all the other ones, suggesting the explanation argued above. Figure 9 shows a schematic representation of the possible crack pattern with fourteen cracks.

The subsequent decentering of the dome and gravity action plays a less relevant role with respect to shrinkage in the development of cracks, as clearly depicted in Figure 8. Indeed, the cracks with tip's latitude reaching a value higher than that where tensile hoop stresses become compressive (for a hemispherical dome of uniform thickness this theoretically occurs at a latitude θ ∼ = 52 • , see [START_REF] Flügge | Stresses in shells[END_REF]), do not evidently propagate further in the (macroscopic) equilibrium configuration of the dome.

The role of step-rings

In evaluating the effect of step-rings on the state of stress of the Pantheon's dome, the opposite and controversial results given by Mark and Hutchinson [START_REF] Mark | On the Structure of the Roman Pantheon[END_REF] and Brune [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF], as we highlighted in Section 1.3, need explanation. To this purpose, we investigate the static response of the Pantheon under its own weight with and without step-rings, using a 3D and a 2D axi-symmetric model.

In the light of the simulations (see Fig. 10), we observe that the presence of step-rings results in a decrease of the hoop stresses with respect to the model without step-rings; the maximum hoop stress in the former configuration is found to be ∼ 27.1 % lower than the one developped in the latter.

The results we find agree with those reported in [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF], although the percentage of decrease of the hoop stresses reported by the author is higher ∼ 58.5 %. The difference probably comes only from the simplified choice of the material densities made in [START_REF] Ph | The Mechanics of Imperial Roman Concrete and the Structural Design of Vaulted Monuments[END_REF], where the entire structure is subdivided into 3 regions: foundations and cylindrical part with ρ = 1750 kg/m 3 , lowermost and uppermost parts of the dome with ρ = 1500 kg/m 3 and ρ = 1350 kg/m 3 , respectively. While, as explained in Sec. 2, we decided to follow the indications for the densities given in [START_REF] Mark | On the Structure of the Roman Pantheon[END_REF]] and the scheme represented in Figure 3 and Table 1. Moreover, from the cracked configuration of the dome, as found by modeling shrinkage, we can easily check that the dome behaves like an array of wedge-shaped arches and that the hoop stresses are even lower than those of the configuration without stepped rings.

Conclusion

The study presented in this paper concerns an investigation on i) the possible cause of the origin of the meridional cracks that are observed in the dome and ii) the effect of the presence of the step-rings in the structure's state of stress.

The investigation consists of a numerical simulation, carried on an accurate 3D FE model of the Pantheon's structure, where the distinctive geometrical details of the monument, such as the internal dome coffering, the external stepped rings and the caveas in the dome itself, are considered. Furthermore, the different materials used to built the Rotonda, whose characteristics have been derived using published data, are modeled and their behavior is described in terms of a nonlinear constitutive law accounting for tensile softening and damage. Finally, a plausible sequence of the dome's construction is assumed to model the initial stages of the life of the structure.

D R A F T

This research has been motivated by some previous studies, namely [START_REF] Mark | Light, wind and structure[END_REF]Hutchinson, 1986, Brune, 2010] and should be intended as a continuation of them. We point out, in fact, that for its characteristics our study is a step forward with respect to the cited studies: the use of an accurate 3D model, of a nonlinear constitutive law and the simulation of a plausible sequence of construction phases are in fact new with respect to the previous cited studies.

The study presented in this paper shows that the meridional cracks may have been produced in the early stage of the dome's life by the action of concrete shrinkage and gravity.

In fact, we retrieve the same cracking pattern of the one observed in situ: both the cracks spatial distribution (fifteen in number) and their extent agree remarkably well with the observed cracks [K. [START_REF] De Fine Licht | The Rotunda in Rome: a study of Hadrian's Pantheon[END_REF]. Of course, it is not possible to affirm with absolute certainty that concrete shrinkage and gravity are the only responsible for the presence of the meridional cracks, but we can reasonably confirm, with our study, the conjecture suggested by the cited authors: these two causes are sufficient to produce the observed effect and, finally, the conjugate effect of concrete shrinkage and of gravity is likely to be the true reason for the appearence of the meridional cracks in the Pantheon's dome since its first period of life.

We have also investigated the role of the stepped rings on the exterior lower part of the dome. In fact, also in this case the opinions of the researchers diverge. Our study shows that Mark's and Hutchinson's conclusions and Brunes's are complementary rather than contradictory. Indeed, we show that the structural role of the stepped rings is twofold. On one hand, as stated by Brune, they reduce the hoop tensile stresses in the dome and, on the other hand, as stated by Mark and Hutchinson, they provide additional loading to the cantilever-like mechanism formed by the existing meridional cracks. On the whole, they have a positive impact on the structure, improving its stability.

The

  Rotonda internal sphere according to de Fine Licht The Rotonda internal sphere according to Wilson-Jones

Figure 1 :

 1 Figure 1: Scheme and dimensions of the Pantheon (from[START_REF] Pulvirenti | Didatticarte[END_REF]).

Figure 4 :

 4 Figure 4: Geometrical model of the Rotonda and a detail of the dense FE Mesh.

Figure 5 :

 5 Figure 5: Schematic representation of polar and azimuthal angles.

Figure 7 :

 7 Figure 7: Progressive cracking of the dome due to an incrementally applied thermal load of (ε v /α) 5 = 4.55 K, during step 2) (plan view).

Figure 8 :

 8 Figure 8: Final crack patterns at the end of the calculations of steps 2) (left) and 3) (right), for (ε v /α) 5 = 4.55 K.

Figure 9 :

 9 Figure 9: View of the Rotonda and pronaos, left. Possible pattern of 14 cracks (in blue), still formed from the caveas at the base of the dome, due to the presence of the pronaos.

Figure 10 :

 10 Figure 10: Hoop stresses due to self-weight with and without stepped rings: a) 2D axisymmetric, b) 3D model, and c) 3D model at the end of the shrinkage calculations, (ε v /α) 5 = 4.55 K (cracks are not displayed).

Table 1 :

 1 Materials data

	Material	Part	ρ	E	ν	G f	f t
			[kg/m 3 ] [GPa]		[J/m 2 ] [MPa]
	Granite	Columns	2500	55.3 0.16	17.5	3.50
	Concrete 1 Foundations	2000	13.5 0.20	62.1	0.68
	Concrete 2 Cylindrical wall	1750	7.0	0.20	59.4	0.63
	Concrete 3 Lower dome	1600	1.0	0.20	5.0	0.08
	Concrete 4 Intermediate dome	1500	1.0	0.20	5.0	0.08
	Concrete 5 Upper dome	1350	1.0	0.20	5.0	0.08

The Pantheon has, in fact, inspired number of architects during the centuries, especially during the Neo-Classical period, e.g. P. Bianchi in the church San Francesco di Paola in Naples (1816-46), F. Bonsignore in the church Gran Madre di Dio in Turin (1818-31) or T. Jefferson in The Rotunda of the University of Virginia (1822-26).

This situation is typical also of many masonry domes, see e.g.[START_REF] Blasi | Analytical approach to collapse mechanisms of circular masonry arch[END_REF] Foraboschi, 1994, Foraboschi, 2016].


Mohammad Noormohammadpour

Cauligi S Raghavendra

Sriram Rao

Srikanth Kandula

Ming Hsieh

DCCast: Efficient Point to Multipoint Transfers Across Datacenters

Using multiple datacenters allows for higher availability, load balancing and reduced latency to customers of cloud services. To distribute multiple copies of data, cloud providers depend on inter-datacenter WANs that ought to be used efficiently considering their limited capacity and the ever-increasing data demands. In this paper, we focus on applications that transfer objects from one datacenter to several datacenters over dedicated inter-datacenter networks. We present DCCast, a centralized Point to Multi-Point (P2MP) algorithm that uses forwarding trees to efficiently deliver an object from a source datacenter to required destination datacenters. With low computational overhead, DCCast selects forwarding trees that minimize bandwidth usage and balance load across all links. With simulation experiments on Google's GScale network, we show that DCCast can reduce total bandwidth usage and tail Transfer Completion Times (TCT) by up to 50% compared to delivering the same objects via independent point-to-point (P2P) transfers.

Introduction

Increasingly, companies rely on multiple datacenters to improve quality of experience for their customers. The benefits of having multiple datacenters include reduced latency to customers by mapping users to datacenters according to location, increased failure resiliency and availability, load balancing by mapping users to different datacenters and respecting local data laws. Companies may either own the datacenters or depend on infrastructure and services from providers such as Microsoft Azure [START_REF]Microsoft azure: Cloud computing platform & services[END_REF], Google Compute Engine [START_REF]Compute engine -iaas -google cloud platform[END_REF] or Amazon Web Services [START_REF]Amazon web services (aws) -cloud computing services[END_REF]. Large providers use geographically distributed dedicated networks to connect their datacenters [START_REF] Wu | Orchestrating bulk data transfers across geo-distributed datacenters[END_REF][START_REF] Kandula | Calendaring for wide area networks[END_REF][START_REF] Hong | Achieving high utilization with software-driven wan[END_REF][START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF].

Nowadays, many services operate across multiple datacenters. Such services require efficient data transfers among datacenters including replication of objects from

Service Replicas

Facebook Across availability regions [START_REF]Companies like facebook and google have multiple data centers[END_REF], ≥ 4 [START_REF]Where are the facebook servers located worldwide?[END_REF], for various object types including large machine learning configs [START_REF] Tang | Holistic configuration management at facebook[END_REF] CloudBasic SQL Server Up to 4 secondary databases with active Geo-Replication (asynchronous) [START_REF]Geo-replication/multi-ar (active)[END_REF] Azure SQL Database Up to 4 secondary databases with active Geo-Replication (asynchronous) [START_REF]Overview: Sql database active geo-replication[END_REF] Oracle Directory Server Up to the number of datacenters owned by an enterprise for regional load balancing of directory servers [START_REF]Using replication across multiple data centers[END_REF][START_REF]Understanding oracle internet directory replication[END_REF] AWS Route 53 GLB Across multiple regions and availability zones for global load balancing [START_REF]Global load balancing using aws route 53[END_REF] Youtube Function of popularity, content potentially pushed to many locations (could be across ≥ 33 datacenters [START_REF] Torres | Dissecting video server selection strategies in the youtube cdn[END_REF]) Netflix Across 2 to 4 availability regions [START_REF]How netflix leverages multiple regions to increase availability (arc305[END_REF], and up to 233 cache locations [START_REF]Mapping netflix: Content delivery network spans 233 sites[END_REF] Table 1: Various Services Using Replication one datacenter to multiple datacenters which is referred to as geo-replication [START_REF] Wu | Orchestrating bulk data transfers across geo-distributed datacenters[END_REF][START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF][START_REF] Gupta | Mesa: A georeplicated online data warehouse for google's advertising system[END_REF][START_REF] Kraska | Mdcc: Multi-data center consistency[END_REF][START_REF] Jin | Optimizing bulk transfers with software-defined optical wan[END_REF][START_REF] Zhao | The prospect of inter-data-center optical networks[END_REF][START_REF] Gifre | Experimental assessment of inter-datacenter multicast connectivity for ethernet services in flexgrid networks[END_REF][START_REF] Miyao | An overlay architecture of global inter-data center networking for fast content delivery[END_REF][START_REF] Laoutaris | Delay-tolerant bulk data transfers on the internet[END_REF][START_REF] Lu | Highly efficient data migration and backup for big data applications in elastic optical inter-data-center networks[END_REF][START_REF] Chen | A first look at inter-data center traffic characteristics via yahoo! datasets[END_REF][START_REF] Feng | Jetway: Minimizing costs on inter-datacenter video traffic[END_REF]. Examples of such transfers include synchronizing search index information [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF], replication of databases [START_REF]Multi-datacenter replication in cassandra[END_REF][START_REF]Azure sql database now supports powerful geo-replication features for all service tiers[END_REF], and distribution of high definition videos across CDNs [START_REF] Feng | Jetway: Minimizing costs on inter-datacenter video traffic[END_REF][START_REF] Kumar Adhikari | Vivisecting youtube: An active measurement study[END_REF][START_REF] Meshenberg | Active-Active for Multi-Regional Resiliency[END_REF][START_REF] Lin | Ecoflow: An economical and deadline-driven inter-datacenter video flow scheduling system[END_REF][START_REF] Roy | Inside the social network's (datacenter) network[END_REF]. Table 1 provides a brief list of how many replicas are made for some applications.

In this paper, we focus on transfers that deliver an object from a source to multiple destinations and call them Point to Multipoint (P2MP) transfers. One solution to make such transfers is to initiate multiple independent point-to-point (P2P) transfers that are scheduled separately [START_REF] Wu | Orchestrating bulk data transfers across geo-distributed datacenters[END_REF][START_REF] Kandula | Calendaring for wide area networks[END_REF][START_REF] Laoutaris | Delay-tolerant bulk data transfers on the internet[END_REF][START_REF] Lin | Ecoflow: An economical and deadline-driven inter-datacenter video flow scheduling system[END_REF][START_REF] Wang | Multiple bulk data transfers scheduling among datacenters[END_REF][START_REF] Yu | Ssnf: Shared datacenter mechanism for inter-datacenter bulk transfer[END_REF][START_REF] Laoutaris | Inter-datacenter bulk transfers with netstitcher[END_REF][START_REF] Feng | Postcard: Minimizing costs on inter-datacenter traffic with store-and-forward[END_REF][START_REF] Nandagopal | Lowering inter-datacenter bandwidth costs via bulk data scheduling[END_REF][START_REF] Yao | On fast and coordinated data backup in geo-distributed optical interdatacenter networks[END_REF][START_REF] Zhang | Guaranteeing deadlines for inter-datacenter transfers[END_REF][START_REF] Noormohammadpour | Dcroute: Speeding up inter-datacenter traffic allocation while guaranteeing deadlines[END_REF]. There may however be more efficient ways, in terms of total bandwidth usage and transfer completion times, to perform P2MP transfers by sending at most one copy of the message across any link given that the source datacenter and destination datacenters are known apriori. We present an elegant solution using minimum weight Steiner Trees [START_REF] Hwang | Steiner tree problems[END_REF] for P2MP transfers that achieves reduced bandwidth usage and tail completion times.

Another approach would be to select trees that connect from sources to all destinations and complete transfers using store-and-forward [START_REF] Laoutaris | Delay-tolerant bulk data transfers on the internet[END_REF][START_REF] Wang | Multiple bulk data transfers scheduling among datacenters[END_REF][START_REF] Yu | Ssnf: Shared datacenter mechanism for inter-datacenter bulk transfer[END_REF][START_REF] Laoutaris | Inter-datacenter bulk transfers with netstitcher[END_REF][START_REF] Feng | Postcard: Minimizing costs on inter-datacenter traffic with store-and-forward[END_REF]. This will impose the overhead of transferring and storing additional copies of objects on intermediate datacenters during the delivery process incurring storage costs as the number of transfers increase, and wasting intra-datacenter bandwidth since such objects have to be stored on a server inside the intermediate datacenters.

Alternatively one can use multicast protocols, which are designed to form group memberships, provide support for members to join or leave, and manage multicast trees as users come and go [START_REF] Cotton | Iana guidelines for ipv4 multicast address assignments[END_REF][START_REF] Keshav | Centralized multicast[END_REF]. These approaches involve complex management algorithms and protocols to cope with changes in multicast group membership [START_REF] Chu | A case for end system multicast[END_REF][START_REF] Quinn | Ip multicast applications: Challenges and solutions[END_REF] which are unnecessary for our problem given that the participants of each P2MP transfer are fixed.

Application layer multicast techniques [START_REF] Chu | A case for end system multicast[END_REF][START_REF] Banerjee | Scalable application layer multicast[END_REF] reduce the implementation and management complexity by creating an overlay network across the multicast group. However, since these methods are typically implemented in end-host applications, they lack full visibility to underlying network properties and status, such as topology and available bandwidth, and may still send multiple copies of packets along the same links wasting bandwidth.

How can one efficiently perform P2MP transfers? Objective is minimizing tail Transfer Completion Times (TCT) considering limited available bandwidth of networks connecting datacenters and the many transfers that share the network which arrive in an online manner. Also, the system does not have prior knowledge of incoming P2MP transfers; therefore, any solution has to be fast and efficient to deal with them as they arrive.

To perform a P2MP transfer, traffic can be concurrently sent to all destinations over a minimum weight Steiner Tree that connects the source and destinations with transfers' demands as link weights. We refer to such trees as forwarding trees using which we can reduce total bandwidth usage. A central controller with global view of network topology and distribution of load [START_REF] Kandula | Calendaring for wide area networks[END_REF][START_REF] Hong | Achieving high utilization with software-driven wan[END_REF][START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF][START_REF] Kumar | Flexible, hierarchical bandwidth allocation for wan distributed computing[END_REF][START_REF] Jalaparti | Dynamic pricing and traffic engineering for timely inter-datacenter transfers[END_REF][START_REF] Jin | Optimizing bulk transfers with software-defined optical wan[END_REF] can carefully weigh out various options and select forwarding trees for transfers.

We can implement forwarding trees using SDN [START_REF] Mckeown | Software-defined networking[END_REF] capable switches that support Group Tables [START_REF] Pfaff | Openflow switch specification[END_REF][START_REF]Understanding how the openflow group action works[END_REF] such as [START_REF]Openflow v1.3.1 compliance matrix for devices running junos os[END_REF][START_REF]S12700 series agile switches[END_REF][START_REF]Hp 5920 & 5900 switch series openflow command reference[END_REF][START_REF]Hp 5130 ei switch series openflow configuration guide[END_REF]. Using this feature, a packet can be replicated and supplied to multiple buckets each processing and forwarding it to a required output switch port. A group might have many buckets, for example one vendor supports up to 32 [START_REF]Understanding how the openflow group action works[END_REF]. There is growing vendor support for group tables as later OpenFlow standards are adopted. In this paper, we use abstract simulations to verify our techniques. In the future, we plan on implementing for-

S D D

Completion Time T T T 2T

Total BW 3X 4X

X: Object Size, R: Link Throughput, T:

X/R S D D X X X X X X

Forwarding Trees

One-to-One Transfers

1 2
Figure 1: Benefits of using Forwarding Trees warding trees using Group Tables.

Motivating Example: In Figure 1, an object X is to be transferred from datacenter S to two D datacenters considering a link throughput of R. In order to send X to destinations, one could initiate individual transfers, but that wastes bandwidth and increases delivery time since the link attached to S turns into a bottleneck.

In this paper, we present an efficient scheme for P2MP transfers called DCCast. It selects forwarding trees according to a weight assignment that tries to balance load across the network. In addition, it uses temporal planning [START_REF] Kandula | Calendaring for wide area networks[END_REF] and schedules P2MP requests on a first come first serve (FCFS) basis to provide guarantees on completion times. FCFS is shown to reduce tail completion times under light-tailed job size distribution [START_REF] Alexander | Largest weighted delay first scheduling: Large deviations and optimality[END_REF][START_REF] Wierman | Is tail-optimal scheduling possible?[END_REF] (optimal discipline depends on this distribution [START_REF] Wierman | Is tail-optimal scheduling possible?[END_REF]).

A related concept is Coflows [START_REF] Chowdhury | Coflow: A networking abstraction for cluster applications[END_REF] that improve performance by jointly scheduling groups of flows with a collective objective. A P2MP transfer can be viewed as a coflow; however unlike other coflows, P2MP transfers present a better opportunity for optimization since the same data is being delivered to different destinations. Using this, DCCast provides the added benefit of reduced bandwidth usage.

We conducted extensive simulation experiments to evaluate DCCast compared with other strategies for picking forwarding trees and scheduling techniques. We performed simulations using synthetic traffic over the Google's GScale topology [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF] with 12 nodes and 19 edges and random topologies with 50 nodes and 150 edges. Our evaluation metrics include bandwidth usage as well as mean and tail TCT. Our current solution assumes the same class of service for all transfers. In a general setting, transfers may have different priorities and should be allotted resources accordingly (e.g. near real-time video vs. cross-region backups).

We evaluated various forwarding tree selection meth-ods. Clearly, there is benefit in carefully picking trees and we observed up to 43% improvement in completion times while using DCCast compared to random tree selection and up to 29% compared to selection of trees that minimize the maximum load over any edge. We compared DCCast with P2P schemes by viewing each P2MP transfer as multiple independent transfers and using multipathing (K shortest paths) to spread the load. For GScale topology and with 2 to 6 destinations per transfer, DCCast reduced both bandwidth usage and tail TCT by over 20% to 50%, respectively, while providing guarantees to users on completion times.

In summary, our contributions are the following:

• Prior work based on traffic scheduling and rate allocation [START_REF] Kandula | Calendaring for wide area networks[END_REF][START_REF] Hong | Achieving high utilization with software-driven wan[END_REF][START_REF] Kumar | Flexible, hierarchical bandwidth allocation for wan distributed computing[END_REF] uses individual point to point transfers to deliver the same object to multiple places. We improve on this by using forwarding trees.

• Prior work on multicasting [START_REF] Cotton | Iana guidelines for ipv4 multicast address assignments[END_REF][START_REF] Keshav | Centralized multicast[END_REF][START_REF] Chu | A case for end system multicast[END_REF][START_REF] Quinn | Ip multicast applications: Challenges and solutions[END_REF][START_REF] Banerjee | Scalable application layer multicast[END_REF] is focused on managing multicast groups. With apriori knowledge of transfer destinations and demands, DCCast builds forwarding trees that are more efficient.

• DCCast minimizes packet reordering and provides guarantees on completion times.

Problem Formulation

The list of variables and their definitions is provided on table 2. To allow for flexible bandwidth allocation, we consider a slotted timeline [START_REF] Kandula | Calendaring for wide area networks[END_REF][START_REF] Zhang | Guaranteeing deadlines for inter-datacenter transfers[END_REF][START_REF] Noormohammadpour | Dcroute: Speeding up inter-datacenter traffic allocation while guaranteeing deadlines[END_REF] where the transmission rate of senders is constant during each timeslot, but can vary from one timeslot to next. This can be achieved via rate-limiting at end-hosts [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF][START_REF] Kumar | Flexible, hierarchical bandwidth allocation for wan distributed computing[END_REF]. A central scheduler is assumed that receives transfer requests from endpoints, calculates their temporal schedule, and informs the end-points of rate-allocations when a timeslot begins. We focus on scheduling large transfers that take more than a few timeslots to finish and therefore, the time to submit a transfer request, calculate the routes, and install forwarding rules is considered negligible in comparison. We assume equal capacity for all links in an online scenario where requests may arrive anytime.

DCCast

Forwarding Trees: Our proposed approach is, for each P2MP transfer, to jointly route traffic from source to all destinations over a forwarding tree to save bandwidth. Using a single forwarding tree for every transfer also minimizes packet reordering which is known to waste CPU and memory resources at the receiving ends especially at high rates [START_REF] Geng | Juggler: a practical reordering resilient network stack for datacenters[END_REF][START_REF] Raiciu | How hard can it be? designing and implementing a deployable multipath tcp[END_REF]. To perform a P2MP transfer R with volume V R , the source S R transmits traffic over a Steiner Tree that spans across D R D R D R . At any timeslot,

Variable Definition R A P2MP transfer V R Volume of R in bytes S R Source datacenter of R D R D R D R Set of destinations of R G
The inter-datacenter network graph

T A Steiner Tree [43] E G E G E G Set of edges of G E T E T E T Set of edges of T L e
Total load currently scheduled on edge e B e (t)

Available bandwidth on edge e at timeslot t W Width of a timeslot in seconds Table 2: Definition of Variables traffic for any transfer flows with the same rate over all links of a forwarding tree to reach all the destinations at the same time. The problem of scheduling a P2MP transfer then translates to finding a forwarding tree and a transmission schedule over such a tree for every arriving transfer in an online manner. A relevant problem is the Minimum Weight Steiner Tree [START_REF] Hwang | Steiner tree problems[END_REF] that can help minimize total bandwidth usage with proper weight assignment. Although it is a hard problem, heuristic algorithms exist that often provide near optimal solutions [START_REF] Robins | Tighter bounds for graph steiner tree approximation[END_REF][START_REF] Watel | A Practical Greedy Approximation for the Directed Steiner Tree Problem[END_REF].

Scheduling Discipline: When forwarding trees are found, we schedule traffic over them according to First Come First Serve (FCFS) policy using all available residual bandwidth on links to minimize the completion times. This allows us to provide guarantees to users on when their transfers will complete upon their arrival. We do not use a preemptive scheme, such as Shortest Remaining Processing Time (SRPT), due to practical concerns: larger transfers might get postponed over and over which might lead to the starvation problem and it is not possible to make promises on exactly when a transfer would complete. Optimal scheduling discipline to minimize tail times rests on transfer size distribution [START_REF] Wierman | Is tail-optimal scheduling possible?[END_REF].

Algorithms: DCCast is made of two algorithms1 . Update() is executed upon beginning of every timeslot. It simply dispatches the transmission schedule, that is the rate for each transfer, to all senders to adjust their rates via rate-limiting and adjusts L e (e ∈ E G E G E G ) by deducting the total traffic that was sent over e during current timeslot.

Allocate(R) is run upon arrival of every request which finds a forwarding tree and schedules R to finish as early as possible. Pseudo-code of this function has been shown in Algorithm 1. Statically calculating minimal forwarding trees might lead to creation of hot-spots, even if there exists one highly loaded edge that is shared by all of such trees. As a result, DCCast adaptively chooses a forwarding tree that reduces the tail transfer completion times while saving considerable bandwidth. It is possible that larger trees provide higher available bandwidth by using longer paths through least loaded edges, but using which would consume more overall bandwidth since they send same traffic over more edges. To model this behavior, we use a weight assignment that allows balancing these two possibly conflicting objectives. The weights represent traffic load allocated on links. Selecting links with lower weights will improve load balancing that would be better for future requests. The tradeoff is in avoiding heavier links at the expense of getting larger trees for even distribution of load.

Algorithm 1: Allocate(R) Input: R(V R , S R ,D R D R D R ), G,
The forwarding tree T selected by Algorithm 1 will have the total weight ∑ e∈E T E T E T (L e + V R ). This weight is essentially the total load over T if request R were to be put on it. Selecting trees with minimal total weight will most likely avoid highly loaded edges and larger trees. To find an approximate minimum weight Steiner Tree, we used GreedyFLAC [START_REF] Watel | A Practical Greedy Approximation for the Directed Steiner Tree Problem[END_REF][START_REF]Evaluation of approximation algorithms for the directed steiner tree problem[END_REF], which is quite fast and in practice provides results not far from optimal.

Evaluation

We evaluated DCCast using synthetic traffic. We assumed a total capacity of 1.0 for each timeslot over every link. The arrival of requests followed a Poisson distribution with rate λ P2MP = 1. Demand of every request R was calculated using an exponential distribution with mean 20 added to a constant value of 10 (fixing the minimum demand to 10). All simulations were performed over as many timeslots as needed to finish all requests with arrival time of last request set to be 500 or less. Presented results are normalized by minimum values in each chart. We measure three different metrics: total bandwidth used and mean and tail TCT. The total bandwidth used is the sum of all traffic over all timeslots and all links. The completion time of a transfer is defined as its arrival time to the time its last bit is delivered to the destination(s). We performed simulations using Google's GScale topology [START_REF] Jain | B4: Experience with a globally-deployed software defined wan[END_REF], with 12 nodes and 19 edges, on a single machine (Intel Core i7-6700T and 24 GBs of RAM). All simulations were coded in Java and used Gurobi Optimizer [START_REF]Gurobi Optimization. Gurobi optimizer reference manual[END_REF] to solve linear programs for P2P schemes. We increased the destinations (copies) for each object from 1 to 6 picking recipients according to uniform distribution. Table 3 shows list of considered schemes (first 4 are P2MP schemes and last 2 are P2P).

We tried various forwarding tree selection criteria over both GScale topology and a larger random topology with 50 nodes and 150 edges as shown in Figures 2 and3, respectively. In case of GScale, DCCast performs slightly better than RANDOM and MINMAX in com-

MINMAX

Selects forwarding trees to minimize maximum load on any link. Schedules traffic using FCFS policy §3 RANDOM Selects random forwarding trees. Schedules traffic using FCFS policy §3 BATCHING Batches (enqueues) new requests arriving in time windows of T . At the end of batching windows, jointly schedules all new requests according to Shortest Job First (SJF) policy and picks their forwarding trees using weight assignment of Algorithm 1 SRPT Upon arrival of a new request, jointly reschedules all existing requests and the new request according to SRPT policy §3 and picks new forwarding trees for all requests using weight assignment of Algorithm 1 P2P-SRPT-LP Views each P2MP request as multiple independent point-to-point (P2P) requests. Uses a Linear Programming (LP) model along with SRPT policy §3 to (re)schedule each request over K-Shortest Paths between its source and destination upon arrival of new requests P2P-FCFS-LP Similar to above while using FCFS policy §3 Table 3: Schemes Used for Comparison pletion times while using equal overall bandwidth (not in figure). In case of larger random topologies, DCCast's dominance is more obvious regarding completion times while using same or less bandwidth (not in figure).

We also experimented various scheduling disciplines over forwarding trees as shown in Figure 4. The SRPT discipline performs considerably better regarding mean completion times; it however may lead to starvation of larger transfers if smaller ones keep arriving. It has to compute and install new forwarding trees and recalculate the whole schedule, for all requests currently in the system with residual demands, upon arrival of every new request. This could impose significant rule installation overhead which is considered negligible in our evaluations. It might also lead to lots of packet loss and reordering. Batching improves performance marginally compared to DCCast and could be an alternate road to take. Generally, a smaller batch size results in a smaller initial scheduling while a larger batch size makes it possible to employ collective knowledge of many requests in a batch for optimized scheduling. Batching might be more effective for systems with bursty request arrival patterns. All schemes performed almost similarly regarding tail completion times and total bandwidth usage (not in figure).

In Figure 5 we compare DCCast with a Point-To-Point scheme (P2P-SRPT-LP) using SRPT scheduling policy which uses various number of shortest paths (K) and delivers each copy independently. The total bandwidth usage is close for all schemes when there is only one destination per request. Both bandwidth usage and tail completion times of DCCast are up to 50% less than that of P2P-SRPT-LP as the number of destinations per transfer increases. Although DCCast follows the FCFS policy, its mean completion time is close to that of P2P-SRPT-LP and surpasses it for 6 copies due to bandwidth savings which leave more headroom for new transfers.

In a different experiment, we compared DCCast with P2P-FCFS-LP. DCCast again saved up to 50% bandwidth and reduced tail completion times by up to almost 50% while increasing the number of destinations per transfer.

Computational Overhead: We used a network with 50 nodes and 300 edges and considered P2MP transfers with 5 destinations per transfer. Transfers were generated according to Poisson distribution with arrival times ranging from 0 to 1000 timeslots and the simulation ran until all transfers were completed. Mean processing time of a single timeslot increased from 1.2ms to 50ms per timeslot while increasing λ P2MP from 1 to 10. Mean process-ing time of a single transfer (which accounts for finding a tree and scheduling the transfer) was 1.2ms and 5ms per transfer for λ P2MP equal to 1 and 10, respectively. This is negligible compared to timeslot lengths of minutes in prior work [START_REF] Zhang | Guaranteeing deadlines for inter-datacenter transfers[END_REF].

Conclusions and Future Work

In this paper, we presented DCCast, which aims to reduce the total network bandwidth usage while minimizing transfer completion times using point to multipoint (P2MP) transfers. To save bandwidth, DCCast uses forwarding trees that connect source of a P2MP transfer to its destinations. Selection of forwarding trees is performed in a way that attempts to balance load across the network by avoiding highly loaded links while reducing bandwidth usage by choosing smaller trees. To provide guarantees on transfer completion times, DCCast schedules new traffic to finish as early as possible while not changing the schedule of already allocated transfers. Our evaluations show that DCCast can significantly reduce bandwidth usage compared to viewing each P2MP transfer as multiple independent transfers.

In the future, we would like to perform testbed experiments using traces of real traffic. An alternate scheduling scheme to what we proposed would be Fair Sharing which we aim to study. Next, we would like to evaluate DCCast using a mix of P2MP transfers with different number of destinations to better understand how various applications might interact. It would be interesting to consider multiple classes of traffic with different priorities as well. Moreover, further investigation is needed to measure the fraction of traffic with multiple destinations which benefit from forwarding trees. Finally, it is necessary to study approaches for handling and recovering from failures.

Acknowledgments

We would like to thank our shepherd Sindhu Ghanta and the anonymous reviewers of the HotCloud workshop whose comments helped us greatly improve the quality of this paper.

Discussion Topics

Prior work on inter-datacenter transfers uses a combination of various techniques, such as rate-control [START_REF] Hong | Achieving high utilization with software-driven wan[END_REF][START_REF] Kumar | Flexible, hierarchical bandwidth allocation for wan distributed computing[END_REF], temporal planning [START_REF] Kandula | Calendaring for wide area networks[END_REF], store-and-forward [START_REF] Laoutaris | Delay-tolerant bulk data transfers on the internet[END_REF], and topology changes [START_REF] Jin | Optimizing bulk transfers with software-defined optical wan[END_REF], to improve the performance and efficiency of point-to-point (P2P) inter-datacenter transfers. In this paper, we focused on point-to-multipoint (P2MP) transfers and a new direction in which forwarding trees are used to deliver an object simultaneously to all destinations. We discussed the benefits of this approach and presented evaluations to back up our proposal.

The extent to which our approach can benefit operators as well as cloud and datacenter applications used in industry would be one possible discussion point. This depends partly on the type of applications, desired level of reliability, and customer SLOs such as user access latency. Finally, a crucial factor is the fraction of transfers with multiple destinations, which are ones that can actually benefit from use of forwarding trees.

There are several discussion points regarding implementation. In case of using tools, such as SDN, to cheaply setup and tear down forwarding trees, how can we meet the necessary performance metrics, such as delay, considering number of required forwarding rules, transfer arrival rate, and latency overhead of rule installations? What are possible tensions between performance efficiency and practical feasibility of techniques?

Another topic of discussion would be selection of the forwarding trees. We presented and evaluated three possible selection methods. However selection of forwarding trees that reduce usage of bandwidth while minimizing transfer completion times is an open problem. In addition, would it be better to select and setup trees dynamically, or statically build many trees and use them? Scalability of our approach considering various network topologies, different network sizes as well as arrival rate of transfers, effectiveness of the scheduling discipline used in satisfying users and operators, and handling of network or end-point failures would be other possible discussion topics. Would it be possible to apply known methods of improving scalability if necessary?

Figure 2 :

 2 Figure 2: Tree Selection (GScale Topo)

Figure 3 :Figure 4 :

 34 Figure 3: Tree Selection (Random Topo, |V |= 50)

Figure 5 :

 5 Figure 5: DCCast vs Point-To-Point (P2P-SRPT-LP)

  W , L e and B e (t) for e ∈ E G

	E G E G
	and t > t now
	Output: Forwarding tree (minimum weight Steiner
	Tree) T and Transmission Schedule of R
	for t > t now
	1 To every edge e ∈ E G E G E G , assign weight W e = (L e + V R );
	2 Find the Minimum Weight Steiner Tree T that
	connects S R ∪D R D R D R . We used GreedyFLAC [65, 66];
	3 Schedule R over T to finish as early as possible.
	t ← t now + 1 and V ← V R ;
	while V > 0 do
	B T ← min min min e∈E T E T E T (B e (t )) ;
	Schedule R on T with rate min min min(B T , V W ) at
	timeslot t ;

t ← t + 1 and V ← V -B T ×W ;

return T and the Transmission Schedule of R;

Please find an implementation of DCCast algorithms on Github:https://github.com/noormoha/DCCast