Pierre Michaud
email: pierre.michaud@inria.fr

Best-Offset Hardware Prefetching

Hardware prefetching is an important feature of modern highperformance processors. When the application working set is too large to fit in on-chip caches, disabling hardware prefetchers may result in severe performance reduction. A new prefetcher was recently introduced, the Sandbox prefetcher, that tries to find dynamically the best prefetch offset using the sandbox method. The Sandbox prefetcher uses simple hardware and was shown to be quite effective. However, the sandbox method does not take into account prefetch timeliness. We propose an offset prefetcher with a new method for selecting the prefetch offset that takes into account prefetch timeliness. We show that our Best-Offset prefetcher outperforms the Sandbox prefetcher on the SPEC CPU2006 benchmarks, with equally simple hardware.

INTRODUCTION

Hardware prefetching is an important feature of modern high-performance processors. When the application working set is too large to fit in on-chip caches, disabling hardware prefetchers may result in severe performance loss.

Hardware prefetchers try to exploit certain patterns in applications memory accesses. However, there exists a wide diversity of applications and memory patterns, and many different ways to exploit these patterns.

The simplest hardware prefetchers exploit simple memory access patterns, in particular spatial locality and constant strides. Although simple prefetchers do not perform well on all applications, this kind of access pattern occur frequently, and good prefetchers must perform well on these patterns.

Recently, Pugsley et al. introduced a new sort of prefetcher, offset prefetchers, and the sandbox method for selecting the prefetch offset dynamically [START_REF] Pugsley | Sandbox prefetching: safe run-time evaluation of aggressive prefetchers[END_REF]. Offset prefetching is a generalization of next-line prefetching. Unlike a stream prefetcher, an offset prefetcher does not try to detect streams. Pugsley et al.'s offset prefetcher, SBP, requires simple hardware and is very effective on applications having characteristics similar to the SPEC CPU2006 benchmarks. However, the sandbox method does not take into account prefetch timeliness. Issuing accurate prefetches helps only if prefetches hide a substantial fraction of the miss latency.

The Best-Offset (BO) prefetcher we propose is an offset prefetcher with a new method for selecting the prefetch offset, taking into account prefetch timeliness. We show that the BO prefetcher provides significant speedups over SBP on the SPEC CPU2006, with equally simple hardware 1 .

The paper is organized as follows. Section 2 discusses related work. Section 3 illustrates offset prefetching with some examples. Section 4 describes the proposed Best-Offset prefetcher. Section 5 gives a detailed description of our baseline microarchitecture, with experimental results. Section 6 presents an experimental evaluation of the BO prefetcher. Finally, Section 7 concludes this study.

BACKGROUND

The idea of prefetching is as old as caches, which operate on lines, i.e., blocks of contiguous memory locations, without the guarantee that all the information in a block will actually be used by the program. However, what is called prefetching in processors is usually the speculative fetching of cache lines that have not yet been requested by the program. Prefetching has been studied since the 1970's (see [START_REF] Smith | Cache memories[END_REF] for early references).

We consider hardware-only prefetching in this study. Prefetching can be done at any cache level. Level-1 (L1) and level-2 (L2) prefetching lead to different possibilities and tradeoffs, hence different sorts of prefetchers. An L1 prefetcher can use some informations that it would be somewhat costly to propagate to the L2 cache, such as load/store PCs, virtual addresses, and program order. On the other hand, L1 caches have stronger capacity and bandwidth constraints than L2/L3 caches. L1 caches do not tolerate inaccurate prefetches, while L2/L3 caches do to a certain extent. Best-Offset prefetching is intended for L2 prefetching.

One of the simplest prefetching method, next-line prefetching, prefetches line X + 1 when line X is accessed. A prefetch bit may be added to each cache line to reduce useless prefetches [START_REF] Smith | Cache memories[END_REF]. So and Rechtschaffen proposed to use cache replacement status instead of a prefetch bit [START_REF] So | Cache operations by MRU change[END_REF].

Stride prefetchers try to identify, among load and store instructions, those that access memory with a constant stride [START_REF] Chen | Effective hardware-based data prefetching for high-performance processors[END_REF][START_REF] Fu | Stride directed prefetching in scalar processors[END_REF][START_REF] Sklenar | Prefetch unit for vector operations on scalar computers[END_REF]. Stride prefetchers usually have a table indexed with load/store PCs. An important feature of stride prefetchers is that they issue a prefetch request only if there is a certain confidence that the prefetch will be useful. However, stride prefetchers are more easily implemented at the L1, as they need to see all the memory instructions, including those that hit in the DL1, and preferably in program order.

Stream prefetching was introduced by Jouppi [START_REF] Jouppi | Improving direct-mapped cache performance by the addition of a small fully associative cache and prefetch buffers[END_REF]. It exploits sequential streams, like next-line prefetching, but tries to improve prefetch timeliness and decrease useless prefetches by prefetching several successive lines into a stream buffer when a stream has been detected. Only when a demand access hits on the stream buffer head is the prefetched line moved into the cache (hence reducing cache pollution), and a new line is prefetched to keep the stream buffer full. Several stream buffers are needed for good performance on interleaved streams [START_REF] Jouppi | Improving direct-mapped cache performance by the addition of a small fully associative cache and prefetch buffers[END_REF]. Palacharla and Kessler proposed an off-chip stream prefetcher that can prefetch non-unit stride accesses, each stream being identified by the memory region it is accessing [START_REF] Palacharla | Evaluating stream buffers as a secondary cache replacement[END_REF].

Hagersten proposed ROT, a sophisticated stream prefetcher that can prefetch with non-unit strides [START_REF] Hagersten | Toward scalable cache only memory architectures[END_REF]. ROT detects streams by maintaining a list of popular strides and a list of recent miss addresses, checking for each recent miss if its distance to the current access equals one of the popular strides. The prefetch stream depth is increased dynamically upon late prefetches. The list of popular strides is updated by comparing the current address with recent miss addresses, incrementing a score for each candidate stride. Candidate strides are promoted to popular strides if their score exceeds a threshold.

A variant of stream prefetching that does not use stream buffers prefetches N consecutive lines at a time (N is the prefetch degree) at a certain prefetch distance D in the stream. Some authors have proposed to vary N and/or D dynamically by monitoring prefetch accuracy, cache pollution, prefetch timeliness, which depend on applications characteristics [START_REF] Dahlgren | Fixed and adaptive sequential prefetching in shared memory multiprocessors[END_REF][START_REF] Hur | Memory prefetching using adaptive stream detection[END_REF][START_REF] Srinath | Feedback directed prefetching: improving the performance and bandwidth-efficiency of hardware prefetchers[END_REF]. Hur and Lin have proposed a method for making stream prefetching efficient on short streams [START_REF] Hur | Memory prefetching using adaptive stream detection[END_REF].

The prefetchers mentioned above exploit simple memory access patterns, such as sequential accesses or constant strides. Many prefetchers have been proposed that try to exploit more complex access patterns. For instance, some prefetchers record in a table some history about past memory accesses and use that history to predict future memory accesses [START_REF] Joseph | Prefetching using Markov predictors[END_REF][START_REF] Kandiraju | Going the distance for TLB prefetching: an application-driven study[END_REF][START_REF] Nesbit | Data cache prefetching using a global history buffer[END_REF][START_REF] Nesbit | AC/DC: an adaptive data cache prefetcher[END_REF][START_REF] Somogyi | Spatial memory streaming[END_REF][START_REF] Chou | Low-cost epoch-based correlation prefetching for commercial applications[END_REF][START_REF] Somogyi | Spatio-temporal memory streaming[END_REF][START_REF] Ishii | Access map pattern matching for high performance data cache prefetch[END_REF][START_REF] Jain | Linearizing irregular memory accesses for improved correlated prefetching[END_REF][START_REF] Kim | Multiple stream tracker: a new hardware stride prefetcher[END_REF] (this list is not exhaustive).

Recently, Pugsley et al. introduced Sandbox prefetching [START_REF] Pugsley | Sandbox prefetching: safe run-time evaluation of aggressive prefetchers[END_REF]. The Sandbox prefetcher prefetches line X + D when line X is requested at the L2, where D is adjusted dynamically by performing "fake" prefetches in a Bloom filter. This is not a stream prefetcher, but what Pugsley et al. call an offset prefetcher. A fundamental difference between offset prefetchers and stream prefetchers is that offset prefetchers do not try to detect streams. Pugsley et al. show that, on the SPEC CPU2006, the Sandbox prefetcher matches or even slightly outperforms the more complex AMPM prefetcher that won the 2009 Data Prefetching Championship [START_REF] Ishii | Access map pattern matching for high performance data cache prefetch[END_REF][START_REF]DPC-1. 1st JILP Data Prefetching Championship[END_REF].

The Sandbox prefetcher, however, does not take into account prefetch timeliness. The Best-Offset prefetcher we propose is an offset prefetcher that takes into account prefetch timeliness.

OFFSET PREFETCHING

Offset prefetching is a generalization of next-line prefetching [START_REF] Smith | Cache memories[END_REF]. When a line of address X is requested by the core, an offset prefetcher prefetches line X + D, where D is the prefetch offset. The case D = 1 corresponds to next-line prefetching.

The optimal offset value is not the same for all applications. A full-fledged offset prefetcher has an offset selection mechanism for setting dynamically the offset depending on application behavior. To the best of our knowledge, the first published full-fledged offset prefetcher is the Sandbox prefetcher by Pugsley et al. [START_REF] Pugsley | Sandbox prefetching: safe run-time evaluation of aggressive prefetchers[END_REF]. However, the offset selection mechanism in the Sandbox prefetcher ignores prefetch timeliness. The Best-Offset (BO) prefetcher we introduce takes into account prefetch timeliness.

This section provides some examples illustrating why offset prefetching is an effective prefetching technique. The following examples assume 64 byte lines. For convenience, lines accessed in a memory region are represented with a bit vector, adjacent bits representing adjacent lines. The bit value tells whether the line is accessed ("1") or not ("0"). We ignore the impact of page boundaries and consider only the steady state on long access streams.

Example 1: sequential stream

Consider the following sequential stream: 111111111111111111... That is, the lines accessed by the program are X, X+1, X+2, and so on. A next-line prefetcher yields 100% prefetch coverage and accuracy on this example. However, issuing a prefetch for X+1 just after the access to X might be too late to cover the full latency of fetching X+1 from the last-level cache or from memory, leading to a late prefetch. Late prefetches may accelerate the execution, but not as much as timely prefetches. An offset prefetcher yields 100% prefetch coverage and accuracy on sequential streams, like a next-line prefetcher, but can provide timely prefetches if the offset is large enough.

Another factor that may degrade prefetch coverage is scrambling, i.e., the fact that the chronological order of memory accesses may not match the program order exactly [START_REF] Ishii | Access map pattern matching for high performance data cache prefetch[END_REF]. In general, on long sequential streams, tolerance to scrambling improves with larger offsets.

Example 2: strided stream

Consider a load instruction accessing an array with a constant stride of +96 bytes. With 64-byte cache lines, the lines accessed in a memory region are: 110110110110110110... If there is no stride prefetcher at the L1 (or if it issues late prefetches), a delta correlation prefetcher observing L2 accesses (such as AC/DC [START_REF] Nesbit | AC/DC: an adaptive data cache prefetcher[END_REF]) would work perfectly here, as the sequence of line strides is periodic (1,2,1,2,...). Still, a simple offset prefetcher with a multiple of 3 as offset yields 100% coverage and accuracy on this example.

Offset prefetching can in theory provide 100% coverage and accuracy on any periodic sequence of line strides, by setting the offset equal to the sum of the strides in a period, or to a multiple of that number.

Example 3: interleaved streams

Consider two interleaved streams S1 and S2 accessing different memory regions and having different behaviors: S1: 101010101010101010... S2: 110110110110110110... Stream S1 alone can be prefetched perfectly with a multiple of 2 as offset. Stream S2 alone can be prefetched perfectly with a multiple of 3 as offset. Both streams can be prefetched perfectly with a multiple of 6 as offset.

BEST-OFFSET (BO) PREFETCHING

A schematic view of a BO prefetcher is shown in Figure 1. Symbol D in Figure 1 represents the current prefetch offset, which is the offset currently used for prefetching. When a read request for line X accesses the L2 cache, if this is a miss or a prefetched hit (i.e., the prefetch bit is set), and if X and X + D lie in the same memory page, a prefetch request for line X + D is sent to the L3 cache.

Best-offset learning

The prefetch offset D is set automatically and dynamically, trying to adapt to the application behavior, which may vary over time.

The best-offset learning algorithm tries to find the best prefetch offset by testing several different offsets. An offset d is potentially a good prefetch offset if, when line X is accessed, there was in the recent past a previous access for line Xd. However, the fact that Xd was recently accessed is not sufficient for guaranteeing that line X would have been prefetched in time. We want prefetches to be timely whenever possible. I.e., for d to be a good prefetch offset for line X, line Xd must have been accessed recently, but not too recently. Ideally, the time between the accesses to lines Xd and X should be greater than the latency for completing a prefetch request.

Our solution is to record in a recent requests (RR) table the base address of prefetch requests that have been completed. The base address is the address that was used to trigger the prefetch request: if the prefetched line is X + D, the base address is X. The base address is obtained by subtracting the current prefetch offset from the address of the prefetched line inserted into the L2 2 .

If line Xd is in the RR table, it means that a prefetch request for line Xd + D was recently issued and has been completed. Therefore, if a prefetch request had been issued with offset d instead of D, it would have been a prefetch for the line X currently accessed, and this prefetch would have been timely (assuming that the latency of fetching line X equals the latency of fetching line Xd + D).

Several implementions are possible for the RR table. In this study, we choose the simplest implementation: the RR table is direct mapped, accessed through a hash function, each table entry holding a tag. The tag does not need to be the full address, a partial tag is sufficient.

Besides the RR table, the BO prefetcher features an offset list and a score table. The score table associates a score with every offset in the offset list. The score value is between 0 and SCOREMAX (for instance, SCOREMAX=31 means 5bit scores).

The prefetch offset is updated at the end of every learning phase. A learning phase consists of several rounds. At the start of a learning phase, all the scores are reset to 0. On every eligible L2 read access (miss or prefetched hit), we test an offset d i from the list. If Xd i hits in the RR table, the score of offset d i is incremented. During a round, each offset in the list is tested once: we test d 1 on the first access in the round, d 2 on the next access, then d 3 , and so on. When all the offsets in the list have been tested, the current round is finished, and a new round begins from offset d 1 again.

The current learning phase finishes at the end of a round when either of the two following events happens first: one of the scores equals SCOREMAX, or the number of rounds equals ROUNDMAX (a fixed parameter). When the learning phase is finished, we search the best offset, i.e., the one with the highest score 3 . This offset becomes the new prefetch offset, and a new learning phase starts.

Offset list

Nothing prevents a BO prefetcher to use negative offset values. Although some applications might benefit from negative offsets, we did not observe any benefit in our experiments. Hence we consider only positive offsets in this study.

Useful offset values depend on the memory page size, as the BO prefetcher does not prefetch across page boundaries. For instance, assuming 4KB pages and 64B lines, a page contains 64 lines, and there is no point in considering offset values greater than 63. However, it may be useful to consider offsets greater than 63 for systems having superpages.

The choice of offsets to include in the offset list is somewhat arbitrary. For instance, a possibility would be to include all the offsets between 1 and a maximum offset. This maximum offset cannot be too large however, as a big offset list means a big score table and a long learning phase. If we want the list to contain large offsets without the list being too big, we must sample the offsets between 1 and the maximum offset (which requires to implement the offset list as a ROM).

Microarchitects working with thousands of representative benchmarks might want to do an extensive exploration of offsets to put in the list. We do not have enough benchmarks for such exploration to make sense 4 .

We propose a method for offset sampling that is algorithmic and not totally arbitrary: we include in our list all the offsets between 1 and 256 whose prime factorization does not contain primes greater than 5. This gives the following list of 52 offsets: Considering only offsets with small prime factors has two benefits:

• Small offsets are more represented than large ones (small offsets are more likely to be useful).

• The offset list is much smaller than the full offset range.

Moreover, this method is consistent with the example of Section 3.3: if two offsets are in the list, so is their least common multiple (provided it is not too large).

Prefetch throttling

The BO prefetcher is a degree-one prefetcher: it issues at most one prefetch per access.

One could imagine an offset prefetcher with a prefetch degree greater than one. For instance, a degree-two offset prefetcher would prefetch with two different offsets simultaneously, the best and second best offsets. This might bring some extra performance on applications with irregular access patterns. However, this would increase the number of prefetch requests, putting more pressure on memory bandwidth and cache tags bandwidth 5 , unless a prefetch filter is implemented. There is no need for a prefetch filter with a degreeone BO prefetcher. Moreover, prefetching with two offsets may generate many useless prefetches on irregular memory access patterns.

Still, BO prefetching is relatively aggressive compared to some other prefetching methods such as stride prefetching. The useless prefetches issued on irregular access patterns waste energy and memory bandwidth.

The best score obtained at the end of a learning phase gives some information about prefetch accuracy. If the score is very low, it probably means that offset prefetching fails, and we may decide to turn prefetch off.

We define a fixed threshold, BADSCORE, such that when the best score is not greater than BADSCORE, prefetch is turned off. However, best-offset learning never ceases, it continues even when prefetch is off, so that prefetch can be turned on again whenever the application behavior changes and requires prefetching.

Figure 1 illustrates the case where prefetch is on: for every prefetched line Y inserted into the L2, we write address Y -D into the RR table (if Y and Y -D lie in the same page). During learning phases when prefetch is off, insertion in the RR table is modified: for every fetched line Y , we write address Y in the RR table (i.e., D = 0).

Implementation details

The BO prefetcher features 3 adders, shown in Figure 1. These adders need only produce the position of a line inside a page. For instance, with 4MB pages and 64B lines, each adder is 22 -6 = 16 bit wide. The page number bits are simply copied from the base address X or from the prefetched line address Y (cf. Figure 1).

The RR table is accessed through a simple hash function. For instance, for a 256-entry RR table, we XOR the 8 least significant line address bits with the next 8 bits to obtain the table index. For 12-bit tags, we skip the 8 least significant line address bits and extract the next 12 bits.

BASELINE MICROARCHITECTURE

The microarchitecture simulator used for this study is an in-house simulator based on Pin [START_REF] Luk | Pin : building customized program analysis tools with dynamic instrumentation[END_REF]. The operating system activity is not simulated. The simulator is trace driven and does not simulate the effects of wrong-path instructions.

The benchmarks used for this study are the SPEC CPU 2006. A trace is generated for each benchmark. Each trace consists of 20 samples stitched together. Each sample represents 50 million instructions executed consecutively. The samples are spaced regularly throughout the whole benchmark execution. In total, 1 billion instructions are simulated per benchmark.

Unlike a branch predictor or a cache replacement policy, a hardware prefetcher cannot be evaluated as a stand-alone mechanism, as it interacts with other parts of the microarchitecture in a very complex way. This is one of the reasons why it is sometimes difficult to reproduce published experimental results on prefetching [START_REF] Gracia Pérez | MicroLib: a case for quantitative comparison of micro-architecture mechanisms[END_REF].

This section provides a detailed description of our baseline microarchitecture, with a focus on parts that directly impact prefetching effectiveness.

Table 1 summarizes some of the characteristics of our baseline microarchitecture. The superscalar core is loosely modeled after the Haswell microarchitecture, based on information publicly released by Intel [START_REF]Intel. Intel 64 and IA-32 architectures optimization reference manual[END_REF].

We use 6 variations of the baseline, corresponding to 1,2 and 4 active cores and 2 different memory page sizes (4KB and 4MB). Unless specified otherwise, the simulated microarchitecture parameters are those of Table 1.

Baseline IPCs

Our baseline microarchitecture is a quad-core with private L2 caches and a shared L3. The caches are non inclusive. We assume a fixed clock frequency, i.e., we do not simulate dynamic voltage and frequency scaling.

This study focuses on single-thread performance. All the performance numbers presented in this paper are from the point of view of a single-thread application running on core 0. However, the IPC ( 3 are idle, core 0 has exclusive access to the whole L3 capacity and memory bandwidth. However, when the other cores are running some application, the IPC of core 0 generally decreases. One reason for this IPC loss is that core 0 experiences more L3 misses because of the competition between cores for the L3 capacity. Another reason is the competition between cores for the memory bus and for DRAM banks, which increases queuing delays (particularly in the memory controller) and degrades DRAM row buffer locality.

To study how these effects impact prefetching effectiveness, we use an artificial micro-benchmark that thrashes the L3 cache by writing a huge array, going through the array quickly and sequentially. We consider 3 configurations in this study:

• 1 active core: only core 0 is active, cores 1, 2, and 3 are idle.

• 2 active cores: core 1 runs an instance of the cachethrashing micro-benchmark, cores 2 and 3 are idle.

• 4 active cores: cores 1, 2 and 3 each run an instance of the micro-benchmark.

We simulate virtual-to-physical address translation by applying a randomizing hash function on the virtual page number. Hence physical addresses generated by core 0 do not depend upon whether other cores are idle or not. This is an approximation of what happens in real systems, but it makes performance analysis easier.

Figure 2 shows the IPCs of the 29 SPEC CPU2006 benchmarks for the 6 baseline configurations, corresponding to 1, 2, and 4 active cores, 4KB pages and 4MB pages 6 .

The IPC is generally higher with 4MB pages than with 4KB pages, owing to fewer TLB1 and TLB2 misses.

The IPC of core 0 generally decreases when other cores execute the cache-thrashing micro-benchmark. Nevertheless, some benchmarks are more sensitive than others. Even though we tried to provide fairness (see sections 5.2 and 5.3), activity on other cores reduces the IPC of core 0 quite substantially on certain benchmarks (e.g., 462.libquantum). This allows us to evaluate prefetching when the effective L3 capacity and memory bandwidth available to core 0 is smaller.

L3 cache replacement policy

Replacement policies such as DIP [START_REF] Qureshi | Adaptive insertion policies for high-performance caching[END_REF] or DRRIP [START_REF] Jaleel | High performance cache replacement using re-reference interval prediction (RRIP)[END_REF] have been proposed for L2 and L3 caches. We experimented with these policies at the L2 cache but did not observe any significant performance gain over LRU. Still, we found that important performance gains can be obtained by making the L3 replacement policy prefetch-aware (confirming previous studies [START_REF] Lin | Reducing DRAM latencies with an integrated memory hierarchy design[END_REF][START_REF] Wang | Guided region prefetching: a cooperative hardware/software approach[END_REF][START_REF] Srinath | Feedback directed prefetching: improving the performance and bandwidth-efficiency of hardware prefetchers[END_REF][START_REF] Wu | PACMan: prefetch-aware cache management for high performance caching[END_REF][START_REF] Seshadri | Mitigating prefetcher-caused pollution using informed caching policies for prefetched blocks[END_REF]) and core-aware.

Our L3 baseline replacement policy, called 5P, uses set sampling and different insertion policies, like the DIP policy [START_REF] Qureshi | Adaptive insertion policies for high-performance caching[END_REF]. We use five different insertion policies:

• IP1: MRU insertion (i.e., classical LRU replacement). • IP2: probabilistic LRU/MRU insertion, aka BIP [START_REF] Qureshi | Adaptive insertion policies for high-performance caching[END_REF].

• IP3: MRU insertion if demand miss, otherwise LRU insertion [START_REF] Smith | Sequentiality and prefetching in database systems[END_REF][START_REF] So | Cache operations by MRU change[END_REF][START_REF] Wang | Guided region prefetching: a cooperative hardware/software approach[END_REF]).

• IP4: MRU insertion if fetched from core with low miss rate, otherwise LRU insertion.

• IP5: MRU insertion if demand miss from core with low miss rate, otherwise LRU insertion.

Upon a cache hit, the hitting block is always moved to the MRU position.

The original DIP policy has only two insertion policies to choose from, and a single counter is sufficient for choosing. With more than two insertion policies, a different mechanism is required. Instead we use a new method. We have one counter C i per insertion policy IP i , i.e., 5 counters here. When a demand-miss block is inserted into a set dedicated to policy IP i , we increment counter C i . The insertion policy selected in the follower sets is the one with the lowest counter value. However, if the counter value could increase without limitation, this mechanism would be unable to adapt to application behavior changes. Hence we limit the counter value, which cannot exceed CMAX. When any counter reaches CMAX, all counter values are halved at the same time. This mechanism, which we call proportional counters, gives more weight to recent events. For our L3 replacement policy, we use five 12-bit counters and a constituency size of 128 sets.

The IP4 and IP5 insertion policies try to protect from eviction the blocks fetched from cores with a low miss rate [START_REF] Michaud | The 3P and 4P cache replacement policies[END_REF]. To evaluate the miss rate, we use four 12-bit proportional counters, one counter per core. When a block is inserted into the L3, the counter associated with the corresponding core is incremented. The four counters are halved whenever one of them reaches CMAX. The miss rate is considered low if the counter value is less than 1/4 the maximum of the 4 counter values. It is considered high otherwise.

Figure 3 shows the impact of replacing the 5P policy with LRU and with DRRIP (4KB pages). With a single active core, P5 slightly outperforms both LRU and DRRIP thanks to the prefetch-aware insertion policy IP3, which is particularly effective on 403.gcc and 473.astar.

When several cores are active, the L3 replacement policy has a more dramatic impact. The core-aware insertion policies IP4 and IP5 are effective at providing fairness in the L3 cache utilization.

Main memory

Our baseline features two memory channels, each with a 64-bit bus clocked at 1/4 the CPU clock frequency. The main memory is loosely modeled after a DDR3 SDRAM (see Table 1). We model neither refresh nor power related parameters (e.g., tFAW). Each DRAM chip has a 1KB row buffer, i.e., a rank of 8 chips has a total 8KB row buffer.

Physical addresses are mapped onto memory as follows. Let a 32 • • • a 6 be the line address bits (a 5 • • • a 0 is the line offset). The mapping for a line is:

Channel ( where ⊕ represents the XOR operation. Each channel has its own memory controller. The two controllers work independently from each other. For fairness, each core has its own read queue and write queue in each controller. The controller selects requests from the queues and schedule them for issue. Once a request is selected, it is issued at the earliest time possible depending on previously selected requests.

For fairness, the scheduler uses a set of four 7-bit proportional counters (see Section 5.2). There is one counter per core. A counter is incremented when a read request from the corresponding core is selected for issue.

The scheduler has 2 modes: steady and urgent. In steady mode, a core is first chosen, the served core, then read or write requests from that core are selected. The proportional counters are used to determine the served core. However, for a good utilization of row buffer locality, the served core is not changed on every scheduling step but only when one of the write queues is full or when there is no pending read request from the served core hitting in an open row buffer. Writes are performed in batches of 16 writes. Write requests are selected out-of-order from the write queue, trying as much as possible to exploit row buffer locality and bank parallelism. For read requests, an FR-FCFS policy is used [START_REF] Rixner | Memory access scheduling[END_REF]. A row is left open after it has been accessed until a subsequent access requires to close it.

The urgent mode is for providing fairness when cores run applications with different miss rates. The urgent mode preempts the steady mode. We define the lagging core as the core with the smallest counter value among those with a nonempty read queue. If the L3 fill queue is not full and if the difference between the served core and lagging core counters exceeds 31, a read request from the lagging core is selected for issue.

The scheduler does not distinguish between demand and prefetch read requests. They are treated equally.

Fill queues and late prefetches

Some microarchitecture simulators implement L2 and L3 MSHRs. MSHRs hold information about pending misses [START_REF] Kroft | Lockup-free instruction fetch/prefetch cache organization[END_REF]. An MSHR entry is deallocated only after the corresponding miss request has been fulfilled. MSHRs are necessary at the DL1 cache for keeping track of loads/stores that depend on a missing block (and that will have to be rescheduled) and for preventing redundant miss requests. However, MSHRs are not necessary at the L2/L3 caches.

Our baseline microarchitecture does not have L2/L3 MSHRs. Instead, we add associative search capability to the fill queues.

A fill queue is a FIFO holding the blocks that are to be inserted in the cache. An entry is allocated in the fill queue when a miss request is issued to the next cache level (or to memory). For instance, when an L1/L2 miss request is issued to the L3, an entry is reserved at the tail of the L2 fill queue (a request is not issued until there is a free entry).

If the miss request hits in the L3 cache, the fetched block is written into the fill queue. Otherwise, if the block misses in the L3, the fill queue entry is released, and the L1/L2 miss request becomes an L1/L2/L3 miss request. Some metadata (a few bits) is associated with each request as it travels through the memory hierarchy, indicating its type (prefetch or demand miss, instruction or data) and in which cache levels the block will have to be inserted.

Before a block in the fill queue can be inserted into the cache, the replacement policy is invoked to determine the cache way. When the block is inserted into the cache, and if the block was requested at smaller cache levels, it is forwarded to them. For instance, upon an L1/L2/L3 data miss, the block is forwarded to the L2 fill queue while being written into the L3 cache. Later, when the block is written into the L2, it is simultaneously forwarded to the DL1 fill queue 7 .

Without L2/L3 MSHRs, we must modify the fill queues for benefiting from late prefetches. When a demand miss hits in a fill queue and the block in the fill queue was prefetched, the miss request is dropped and the block in the fill queue is promoted from prefetch to demand miss. The tag and request type of each fill queue entry are stored in a separate CAM. When a demand miss address is presented to the fill queue, the CAM is searched, and any entry with a matching tag gets promoted.

Before writing a prefetched block in the cache, if the pre- 7 Without fill queues, it would be necessary to coordinate all the cache levels to complete an L1/L2/L3 miss, which would be difficult to implement. fetch was generated by the prefetcher at that cache level (i.e., it has not been promoted in the meantime), we must check the cache tags to make sure that the block is not already in the cache. This check is mandatory for correctness 8 . It should be noted that MSHRs would not obviate the need to do such tag check. Prefetch requests can be cancelled at any time without taking any specific action 9 . In particular, L2 prefetch requests have the lowest priority for accessing the L3 cache. Prefetch requests wait in an 8-entry prefetch queue until they can access the L3 cache. When a prefetch request is inserted into the queue, and if the queue is full, the oldest request is cancelled.

DL1 prefetcher

This study focuses on L2 prefetching. The DL1 prefetcher, though not the focus of this study, impacts the L2 prefetcher:

• The L2 prefetcher input stream includes L1 prefetches.

The L2 prefetcher does not see addresses in the same order with and without the L1 prefetcher.

• L1 prefetch requests have by definition a better latency tolerance than L1 demand miss requests. When the L1 prefetcher does a perfect job, the L2 prefetcher is superfluous.

Our DL1 prefetcher is a stride prefetcher [START_REF] Fu | Stride directed prefetching in scalar processors[END_REF][START_REF] Sklenar | Prefetch unit for vector operations on scalar computers[END_REF][START_REF] Chen | Effective hardware-based data prefetching for high-performance processors[END_REF]. It features a 64-entry prefetch table accessed with the PC (instruc-tion address) of load/store micro-ops. Each entry contains a tag (the PC), a last address lastaddr, a stride, a 4-bit confidence counter and some bits for LRU management. The prefetch table is updated at retirement, not at execution, to guarantee that memory accesses are seen in program order. However, prefetch requests are issued when a load/store accesses the DL1 cache.

When a load/store micro-op retires, it updates its prefetch table entry as follows. If the load/store address currentaddr equals lastaddr + stride, the confidence counter is incremented, otherwise it is reset to zero. Then, the stride is set equal to currentaddrlastaddr, and lastaddr is set to currentaddr. Note that currentaddr and lastaddr are both virtual addresses.

When a load/store accesses the DL1, if this is a miss or a prefetched hit, the prefetch table is looked up. If the load/store has an entry in the table, if the stride is non null and if the confidence counter value equals 15, a prefetch address is computed from the address currentaddr of the loads/store: pre f etchaddr = currentaddr + 16 × stride (we determined the fixed factor 16 empirically). Before issuing a prefetch request, we check in a 16-entry filter that a prefetch request to the same line has not been recently issued. If the prefetch address passes the filter, it accesses the second-level TLB (TLB2) and a physical line address is generated. If there is a TLB2 miss, the prefetch request is dropped 10 . Otherwise, it is issued to the uncore (L2 first, then L3 if L2 miss, then memory if L3 miss).

Figure 4 shows the impact of disabling the L1 prefetcher. The L1 prefetcher brings significant speedups on several benchmarks. The maximum speedup is +39% on 465.tonto with 4MB pages and 4 active cores.

L2 prefetcher

All the different L2 prefetchers considered in this study ignore load/store PCs and work on physical line addresses. They do not have access to TLB or page table information. Prefetch addresses are generated from core request addresses, by modifying the page-offset bits, keeping physical page numbers unchanged.

Our default L2 prefetcher is a simple next-line prefetcher with prefetch bits [START_REF] Smith | Cache memories[END_REF]. Each L2 cache entry contains a prefetch bit, which is set when a prefetched line is inserted into the L2 and which is reset whenever the line is requested by the L1 (L1 miss or L1 prefetch). When a core request for the line of physical address X accesses the L2, if there is a L2 miss or if there is a L2 hit and the prefetch bit is set, a prefetch request for line X + 1 is issued to the L3 (or to memory if L3 miss). The L2 prefetchers considered in this study all use prefetch bits. Prefetch bits prevent many useless prefetch requests.

Figure 5 shows the performance impact of disabling the next-line prefetcher. Next-line prefetching is quite effective. Disabling it hurts performance substantially on several benchmarks. All subsequent simulations have the L2 prefetcher enabled. Unless specified otherwise, the speedup numbers provided are relative to the baselines with L2 next-line 10 We did not simulate TLB prefetching.

BEST-OFFSET PREFETCHING

Table 2 provides the default parameters of the BO prefetcher evaluated in this study.

Figure 6 shows the performance of BO prefetching relative to next-line prefetching. BO prefetching brings significant speedup on more than one third of the CPU2006 benchmarks. The speedup peaks at 2.2 for benchmark 470.lbm with 4MB pages and 2 active cores. The speedup over next-line prefetching is on average more important with 4MB pages than with 4KB pages, because with large pages a few benchmarks benefit greatly from large prefetch offsets.

On average, the speedup of BO prefetching over next-line prefetching is more pronounced when 2 cores are active than when only core 0 is active. Our understanding is that, when core 0 competes with another core for L3 space and memory bandwidth, the L2 miss latency increases because of more L3 misses, longer queuing delays in the memory controller and degraded DRAM row buffer locality. The best offset is generally larger with longer L2 miss latencies, and next-line 0.9 prefetching is relatively less effective. With 4 active cores, the L2 miss latency is even longer, but the reduced memory bandwidth becomes a performance bottleneck for some benchmarks, a problem that prefetching cannot solve.

Figure 7 compares Best-Offset prefetching with fixedoffset prefetching where the fixed offset ranges from 2 to 7. An offset of 1 is clearly not the best fixed offset on the CPU2006 benchmarks. The best fixed offset is 5.

Figure 8 shows, for four chosen benchmarks and a 4MB page size, the speedup of fixed-offset prefetching, where the fixed offset ranges from 2 to 256 (the speedup of BO prefetching is indicated with a horizontal line).

BO prefetching substantially outperform next-line prefetching on these benchmarks. Benchmarks 433.milc, 459.GemsFDTD and 470.lbm exhibit what resembles constant-stride accesses 11 . Benchmark 433.milc has its performance peaks at offset values multiple of 32. Note that 433.milc benefits from very large offsets (provided superpages are used).

Benchmark 459.GemsFDTD has its performance peaks at offset values 29, 59, 88, 117, 147, 176, etc., i.e., not exactly multiples of 29, but close. These offset values are not in our fixed list of 52 offsets, and the BO prefetcher is not able to reach the maximum performance. However, the peaks are not isolated. Some offset values close to the peaks, though not optimal, achieve good performance. Luckily, one of these offsets, 30, happens to be in our offset list.

The behavior of 470.lbm is even more unintuitive. Its performance peaks are at offset values multiple of 5. Yet there are secondary (and much smaller) peaks at multiples of 5 plus 3, and there is a cluster of high-performing offsets between 252 and 254.

Benchmark 462.libquantum has a more regular behavior. It generates long sequential streams and can sustain a relatively high IPC if given enough memory bandwidth. However, prefetch timeliness is crucial here, and large offsets are necessary to hide the memory latency. On this benchmark, the BO prefetcher works imperfectly and does not find the best offset. The reason is that the BO prefetcher strives for prefetch timeliness. The offsets yielding the greatest number of timely prefetches have very large values (above 200). Offset values between 30 and 100 yield fewer timely prefetches, but more late prefetches and greater coverage. This example shows that striving for prefetch timeliness is not always optimal. This is one of the main weaknesses of the BO prefetcher, a problem that future work should try to solve 12 .

Nevertheless, an important conclusion from Figure 8 is that prefetch timeliness is essential for performance. Recall that speedups are relative to the baseline with L2 next-line prefetching, which is already very effective (Figure 5). Although not apparent in Figure 8, the baseline next-line prefetcher yields a high prefetch coverage on these 4 benchmarks (about 75% coverage for 433.milc and 470.lbm, above 90% for 459.GemsFDTD and 462.libquantum). Yet, the performance of next-line prefetching is quite suboptimal because most prefetches are late.

Impact of prefetch throttling

Figure 9 shows the impact on mean speedup of varying parameter BADSCORE. A majority of the CPU2006 benchmarks are not impacted by parameter BADSCORE. From this experiment, we believe that prefetch throttling makes a difference only for a minority of applications. On the CPU2006 benchmarks, it occurs that in the few cases where prefetch throttling makes a difference (mostly 429.mcf), it hurts performance. On the SPEC CPU2006, the optimal value of BADSCORE is clearly less than 5% of ROUNDMAX. A much larger set of benchmarks would be needed to draw definitive conclusions. For subsequent simulations, we use 11 One might expect the L1 stride prefetcher to work well on these benchmarks. This is not the case, for various reasons. See for instance the analysis of 433.milc in [START_REF] Ishii | Access map pattern matching for high performance data cache prefetch[END_REF][START_REF] Kim | Multiple stream tracker: a new hardware stride prefetcher[END_REF]. 12 Changing the offset list by removing offsets above 100 would be an ad hoc solution, not a real solution. BADSCORE=1.

Impact of the RR table

Figure 10 shows the impact on mean speedup of varying the number of entries of the RR table, from 32 to 512 entries. Prefetching effectiveness increases with the RR table size, up to a certain point. A performance gap can be observed with 4KB pages when going from 128 entries to 256 entries. This gap comes from one benchmark, 429.mcf.

Comparison with Sandbox prefetching

To the best of our knowledge, the SBP prefetcher of Pugsley et al. is the first published full-fledged offset prefetcher [START_REF] Pugsley | Sandbox prefetching: safe run-time evaluation of aggressive prefetchers[END_REF]. The SBP prefetcher is cost-effective and was shown to outperform significantly the FDP prefetcher [START_REF] Srinath | Feedback directed prefetching: improving the performance and bandwidth-efficiency of hardware prefetchers[END_REF] on the SPEC CPU2006 benchmarks, and to match or even slightly outperform the more complex AMPM prefetcher [START_REF] Ishii | Access map pattern matching for high performance data cache prefetch[END_REF].

The SBP prefetcher contains two independent ideas: offset prefetching, and sandbox prefetching. Sandbox prefetching is the idea that a prefetcher can be evaluated without it issuing actual prefetch requests. Instead, "fake" prefetch requests are performed by recording them in a structure, which Pugsley et al. proposed to be a Bloom filter. The accuracy of a fake prefetch is evaluated by checking if a subsequent access hits in the Bloom filter. The SBP prefetcher does not take into account prefetch timeliness.

The BO and SBP prefetcher are both offset prefetchers, but they use different offset selection mechanisms. The sandbox is a stand-alone idea that could be used in hybrid prefetching schemes, for choosing dynamically between different sorts of prefetchers, not necessarily offset prefetchers. By contrast, the selection mechanism used in the BO prefetcher is specific to offset prefetching. While our RR table may look superficially like a sort of sandbox, it is not: the sandbox is updated with fake prefetches, while the RR table is updated with actual prefetches.

We implemented the SBP prefetcher as described in the original paper [START_REF] Pugsley | Sandbox prefetching: safe run-time evaluation of aggressive prefetchers[END_REF], but with a few modifications to make the comparison with BO prefetching meaningful. Our SBP uses the same list of offsets as the BO prefetcher (52 positive offsets) and the same number of scores (52). Our SBP uses a 2048-bit Bloom filter indexed with 3 hashing functions. The evaluation period is 256 L2 accesses (miss or prefetched hit). When line X is accessed, we check in the Bloom filter for X, X -D, X -2D and X -3D, incrementing the score on every hit. The original SBP is a degree-N prefetcher. It can issue prefetch requests with several different offsets, provided their scores are above the accuracy cutoffs. It can also issue 1, 2 or 3 prefetch requests for the same offset depending on the score for that offset. This is how SBP tries to compensate for not being able to evaluate prefetch timeliness. However, degree-N prefetching may generate a lot of redundant prefetches. Some redundant prefetches are removed automatically by the mechanisms already in place in our baseline for dealing with late prefetches 13 . Nevertheless, for SBP, we also look up the L2 tags before issuing a prefetch 14 . Apart from this extra L2 tag check and replacing the BO prefetcher with SBP, everything else is unchanged, and the two prefetchers operate in the same conditions.

Figure 11 compares the BO and SBP prefetchers, giving the geometric mean speedups relative to baselines. SBP does outperform the default next-line prefetcher on average, but not as much as the BO prefetcher. Figure 12 gives for each benchmark the speedup of the BO prefetcher relative to the SBP prefetcher. SBP outperforms the BO prefetcher on some benchmarks, but never by a big margin (always within 10%). However, on some benchmarks (429.mcf, 433.milc,...), BO prefetching brings substantial speedups over SBP.

Figure 13 gives the number of DRAM accesses (read or write) per 1000 instructions, comparing 4 configurations: no L2 prefetch, next-line prefetch, BO prefetch, and SBP. The next-line and BO prefetchers generate approximately the same memory traffic. The BO prefetcher generates significantly more memory traffic than SBP on benchmarks 13 Fill queues are associatively searched. So are the prefetch queue and the memory controller read queue before insertion. 14 We assume that tag lookups do not impact performance. 471.omnetpp and 473.astar. On benchmarks 403.gcc and 433.milc, it is the other way around. On other benchmarks, the BO and SBP prefetchers have similar prefetch aggressiveness. The performance differences observed in Figure 12 mostly come from the ability of BO prefetching to take into account prefetch timeliness. SBP tends to select small offsets yielding high prefetch coverage, but with late prefetches and suboptimal performance (cf. Figure 8).

CONCLUSION

The Sandbox prefetcher of Pugsley et al. defines a new class of prefetchers, offset prefetchers, that are very effective despite requiring simple hardware. However, the Sandbox prefetcher does not take into account prefetch timeliness. We propose an offset prefetcher with a new method for selecting the prefetch offset, different from the sandbox method. We showed that our BO prefetcher outperforms the Sandbox prefetcher on the SPEC CPU2006 by taking into account prefetch timeliness.

Future work on offset prefetching will have to solve two problems that we did not address in this study. One problem is the fact that striving for prefetch timeliness is not always optimal, i.e., the Best-Offset prefetcher we presented is imperfect, it does not always find the best prefetch offset. The second problem is more general and concerns most studies about prefetching. Prefetching effectiveness is strongly dependent on application characteristics. We found empirically that, on the SPEC CPU2006, our prefetch throttling parameter BADSCORE could be set very low. There is no guarantee that this is true on a larger set of applications. Future work may try to adjust dynamically the throttling parameter.

2

 2

Figure 1 :

 1 Figure 1: Schematic view of a BO prefetcher.

Figure 2 :

 2 Figure 2: IPC on core 0 for the 6 baseline configurations: 1,2,4 active cores, 4KB page (upper graph), 4MB page (lower graph)

Figure 3 :

 3 Figure 3: Impact of replacing the baseline L3 replacement policy with LRU (upper graph) and with DRRIP (lower graph). Performance is relative to baselines for 4KB pages. The rightmost cluster of each graph is the geometric mean over the 29 benchmarks.

Figure 4 :

 4 Figure 4: Impact of disabling the DL1 stride prefetcher (performance relative to baselines).

Figure 6 :Figure 7 :

 67 Figure 6: BO prefetcher speedup (relative to next-line prefetching baselines).

Figure 8 :

 8 Figure 8: Fixed-offset prefetching with offset ranging from 2 to 256 on benchmarks 433, 459, 470, and 462 (4MB page, 1 active core).

Figure 9 :

 9 Figure 9: BO prefetcher geometric mean speedup, impact of varying BADSCORE.

Figure 10 :

 10 Figure 10: BO prefetcher geometric mean speedup, impact of varying the number of entries of the RR table.

Figure 11 :

 11 Figure 11: Comparison between the BO and SBP prefetchers (geometric mean speedups relative to baselines).

Figure 12 :Figure 13 :

 1213 Figure 12: BO prefetcher speedup relative to SBP.

Table 1 :

 1 average instructions per cycle) of core 0 depends on what the other cores are doing. If cores 1,2 an Baseline microarchitecture

	clock freq.	fixed
	branch pred.	31KB TAGE & 6KB ITTAGE [30]
	I-fetch	1 cache line, 1 taken branch per cycle
	branch misp. penalty	12 cycles (minimum), redirect I-fetch at branch execution
	decode	8 instructions / cycle
	rename	12 micro-ops / cycle
	execution ports	4 INT, 2 FP, 3 addr, 2 loads, 1 INT store data, 1 FP store
		data
	retire	12 micro-ops / cycle
	reorder buffer	256 micro-ops
	issue buffers	INT: 60 micro-ops, FP: 60 micro-ops
	phys. registers	128 INT (12 read, 6 write), 128 FP (5 read, 4 write)
	ld/st queues	72 loads, 42 stores
	MSHR	32 DL1 block requests
	store sets [3]	SSIT 2k, LFST 42 stores
	cache line	64 bytes
	TLB entries	ITLB1: 64, DTLB1: 64, TLB2: 512
	IL1	32KB, 8-way assoc. LRU
	DL1	32KB, 8-way assoc. LRU, write back, 3-cycle lat., 8 banks,
		8 bytes/bank, 2 read + 1 write
	L2 (private)	512KB, 8-way assoc. LRU, write back, 11-cycle lat., 16-
		entry fill queue
	L3 (shared)	8MB, 16-way assoc. 5P, write back, 21-cycle lat., 32-entry
		fill queue
	memory	2 channels, 1 mem. controller / channel
	each channel	64-bit bus, bus cycle = 4 core cycles, 1 rank, 8 chips/rank,
		8 banks/chip, row buffer: 1KB/chip (8KB/rank)
	DDR3 param. (in bus	tCL=11, tRCD=11, tRP=11, tRAS=33, tCWL=8, tRTP=6,
	cycles)	tWR=12, tWTR=6, tBURST=4 (8 beats)
	memory controller	32-entry read queue and 32-entry write queue per core
	DL1 prefetch	stride prefetcher, 64 entries
	L2 prefetch	next line prefetcher
	page size	4KB / 4MB
	active cores	1 / 2 / 4

Table 2 :

 2 BO prefetcher default parameters prefetching.

A tuned version of the BO prefetcher won the

Data Prefetching Championship[START_REF]DPC-2. 2nd Data Prefetching Championship[END_REF].

If the prefetch address and the base address lie in different memory pages, the actual base address is unknown, and the RR table is not written.

In practice, the best offset and best score can be computed incrementally every time a score is updated.

This would be a case of overfitting.

With two different prefetch offsets D 1 and D 2 , redundant prefetch requests are issued when accessing lines X and X + D 1 -D 2 .

This is the only graph showing IPCs in this paper, and the only graph where the 6 baselines can be compared with each other.

Blocks must not be duplicated in the cache.

With MSHRs, cancelling a prefetch request would require to update the MSHR state.

Acknowledgment

This work is partially supported by the European Research Council Advanced Grant DAL No 267175.


Olga Battaïa
email: olga.battaia@isae.fr

Alexandre Dolgui
email: alexandre.dolgui@mines-nantes.fr

Nikolai Guschinsky

Integrated process planning and system configuration for mixed-model machining on rotary transfer machine

Keywords: Rotary machine, Product variety, Machine engineering, Production system design, Integrated process planning and system configuration, Line design and balancing, Combinatorial design, Combinatorial optimization, Industrial case study

New generation of rotary transfer machines processing different models of parts is considered. In order to enhance the cost-effectiveness of mixed-model rotary transfer machines, the problems of process planning for the parts to be machined and the configuration of a rotary transfer machine are integrated in the same optimisation problem. This problem is modelled as a combinatorial optimization problem. The decisions to be taken simultaneously concern the orientation of parts for machining, the machining parameters for processing the parts as well as the configuration of machining units to be used at working positions of the machine. Constraints related to the design of such units -spindle heads, turrets -and working positions, as well as precedence constraints related to machining operations, are taken into account. The problem consists in minimizing an estimated cost of the rotary transfer machine, while reaching a given output and satisfying all the constraints. The proposed methods to solve the problem are based on its MIP formulation. The optimisation techniques are validated on an industrial case study. Numerical experiments evaluate the efficiency of the approach against the variety of parts to be produced.

INTRODUCTION

Within the today's context of increasing demand and product diversification, companies must be able to adapt their manufacturing systems for high variety production in order to profitably produce in small quantities different models of products. Mixed-model production is the practice of processing products without changeovers in the manufacturing system [START_REF] Rabbani | Mixed-model assembly line balancing in assemble-toorder environment with considering express parallel line: problem definition and solution procedure[END_REF]. Such a production mode poses new challenges in production system design, planning and management. In order to be cost-efficient several decision problems have to be considered jointly [START_REF] Leonesio | An integrated approach to support the joint design of machine tools and process planning[END_REF]) such as process planning, system configuration and scheduling. In literature, each of these decision problems has attracted a large amount of research interest [START_REF] Xu | Computer-aided process planning -A critical review of recent developments and future trends[END_REF], Battaïa et al. 2012b[START_REF] Guschinskaya | Minimizing makespan for multispindle head machines with a mobile table[END_REF][START_REF] Dolgui | Optimisation of multi-position machines and transfer lines[END_REF]. However, conventionally they have been performed sequentially [START_REF] Lv | Process planning and scheduling integration with optimal rescheduling strategies[END_REF]. Under the modern production constraints and global competition, the strong dependence between these issues and its influence on the profitability of product manufacturing, resource utilisation and product delivery time cannot be ignored anymore. The growing amount of research work in the direction of joint consideration of these problems proves the importance of such an integrated approach.

It should be noted that the most advanced integration is currently realized between process planning and scheduling [START_REF] Phanden | An approach for integration of process planning and scheduling[END_REF][START_REF] Bensmaine | A new heuristic for integrated process planning and scheduling in reconfigurable manufacturing systems[END_REF]. The primary goal of process planning is to specify raw materials or components, processes and operations needed to convert a part from its raw material to the finished form [START_REF] Yin | A process planning method for reduced carbon emissions[END_REF]. Scheduling receives process plans as its input and defines an order of processing the operations on machines while satisfying the precedence relations given in process plans. Scheduling is bound by process sequencing instructions given by the process plan and constrained by time-phased availability of production resources [START_REF] Li | A simulated annealing-based optimization approach for integrated process planning and scheduling[END_REF]. However, even if a great research effort was dedicated to the integration of process planning and scheduling since the pioneer study by [START_REF] Chryssolouris | An integrated approach to process planning and scheduling[END_REF], it still remains of limited functionality or compensated in computational efficiency due to the NP-hard nature of both problems [START_REF] Mohapatra | A nested partitioning-based approach to integrate process planning and scheduling in flexible manufacturing environment[END_REF]. The existing approaches for these two methods are broadly categorized into two types: the progressive/enumerative approach and the simultaneous/centralised approach. A comprehensive state-ofthe-art review on the integration of process planning and scheduling has been recently realized by [START_REF] Phanden | Integration of process planning and scheduling: a state-of-theart review[END_REF].

The configuration of machine tools and process planning problems are also traditionally managed as independent stages, where the process plan is designed by considering a number of machine tool solutions available from catalogue. Despite the fact that this strategy presents a number of disadvantages in terms of process results and machine capabilities fully exploitation, the integration of these decision problems has been rarer considered in the academic literature. [START_REF] Szadkowski | An approach to machining process optimization[END_REF] has proposed one of the first models to optimize process plans for mass production taking into account combinatorial aspects and machining constraints. A graph approach for optimisation of mass production rotary transfer machines was proposed by [START_REF] Dolgui | Graph approach for optimal design of transfer machine with rotary table[END_REF]. A decision support system for design of mass production machining lines composed of stations with rotary or mobile table was developed by Battaïa et al. (2012a). This decision system included modules for part designing, process planning, system configuration and system cost optimisation. An integrated approach for jointly configuring machine tools and process planning with the objective to optimize the production costs was developed by [START_REF] Leonesio | An integrated approach to support the joint design of machine tools and process planning[END_REF]. The problem of combinatorial customization of automated production lines with rotary transfer and turrets was addressed by Battaïa et al. (2014a). Integrated configurable equipment selection and line balancing for mass production with serial-parallel machining systems was considered by Battaïa et al. (2014b).

The studies considering reconfiguration of machining systems when it is necessary to integrate new parts to be machined requires also solving NP-hard optimization problems. For the case of mass production, where the integration of new parts is not effortless, optimisation techniques were proposed by [START_REF] Makssoud | An exact optimization approach for a Transfer Line Reconfiguration Problem[END_REF]. To improve the flexibility of existing machining systems, several studies were conducted by [START_REF] Terkaj | Focused flexibility in production systems[END_REF][START_REF] Terkaj | A stochastic programming approach to support the machine tool builder in designing focused flexibility manufacturing systems (ffmss)[END_REF] and Copani et al (2015), [START_REF] Copani | DEMAT: sustainability assessment of new flexibility-oriented business models in the machine tools industry[END_REF]. [START_REF] Tolio | Design of flexible transfer lines: A case-based reconfiguration cost assessment[END_REF] have proposed a mathematical model to assess the reconfiguration cost for flexible transfer lines. Varietyoriented design of rotary machining systems used for family part production was discussed by [START_REF] Battaïa | Variety-oriented design of rotary production systems[END_REF].

Since no model available in the literature can be applied for the integrated process planning and system configuration for mixed-model machining on a rotary transfer machine, this paper develops such an optimisation model and evaluates it on an industrial case study.

The rotary transfer machine studied in this paper is used to produce simultaneously d 0 types of parts. Such machines are multi-positional, i.e. the parts are sequentially machined on m 0 (1, 2, …, m 0 ) working positions. One position of the machine (zero position) is exclusively used for loading new billets and unloading finished parts. It is assumed that the parts are loaded in sequence =( 1 ,  2 , …, 0 ) where  i {0, 1, 2, …, d 0 }, i=1, 2, …,  0 ,  0 is multiple to m 0 +1 and  i =0 means that no part is loaded. Using sequence  one can define in one-to-one manner function (i,k) of part number at the k-th working position each time when machining part  i i.e.:

                otherwise. , , if , ) , ( ) , mod( 0 0 0 0 0 k m i k m i k m i k i
At each working position, several machining units (spindle heads or turrets) can be installed to execute the operations assigned to this position. There are verical and horizontal units to process vertivally or horizontally, respectively. A turret holds several machining tools which are applied to the parts to be machined sequentially. A horizontal turret (spindle head) can work in parallel with a vertical spindle head (but not a turret) to access to different sides of parts at a working position. A vertical spindle head can be common for several working positions, i.e. can execute simultaneously operations on all these working positions. However, only one vertical turret can be mounted at one position or one common vertical spindle head can be installed for all working positions. Only one horizontal spindle head or turret can be used per position. For example, the rotary transfer machine in Fig. 1 has one vertical spindle head common for position 1,3,4,5, two horizontal turrets on position 1 and 3, and one horizontal spindle head on position 4.

Fig. 1. A rotary transfer machine with turrets

The rest of paper is organized as follows. Section 2 describes the decision variables and input data for the joint process planning and system configuration problem for mixed-model machining on a rotary transfer machine. Sections 3 provides a mathematical model for the considered combinatorial optimization problem. An industrial example is presented in Section 4. The results of numerical experiments are given and analyzed in Section 5. Concluding remarks are reported in Section 6.

PROBLEM STATEMENT

Notations and definitions

Let N d be the set of machining operations needed for machining elements of the d-th part, d=1, 2, …, d 0 , located on n d sides and d s N , s=1, 2, …, n d , be a subset of opertations for machining elements of the s-th Let subset N k , k=1,...,m, contains the operations from set N assigned to the k-th working position.

Let sets N k1 and N k2 be the sets of operations assigned to working position k that are concerned by vertical and horizontal machining, respectively.

Finally, let b kj be the number of machining modules (not more than b 0 ) of type j (vertical if j=1 or horizontal if j=2) installed at the k-th working position. Subsets N kjl , l=1,...,b kj contain the operations from set N kj assigned to the same machining module.

The machining process imposes numerous constraints that have to be taken into account both for process planning and machining units' configuration. In the literature, these constraints are commonly divided in the following categories (Battaïa and Dolgui, 2013).

Since the machining operations naturally have precedence relationships, they have to be taken into account on the process planning step. They are expressed by a directed graph G OR =(N,D OR ) where an arc (p,q)D OR if and only if operation p has to be executed before operation q. It should be noted that if such operations p and q belong to different sides of the part then they cannot be executed at the same position.

Tolerance constraints impose to execute certain operations at the same working position, by the same turret, by the same spindle head or even by the same spindle (for different parts). Such inclusion constraints are modeled by undirected graphs G SP =(N,E SP ), G ST =(N,E ST ), G SM =(N,E SM ) and G SS =(N,E SS ), where edge (p,q)E SS ((p,q)E SM , (p,q)E ST , (p,q)E SP ) if and only if operations p and q must be executed by the same spindle, machining module, turret, or at the same position, respectively.

On contrary, certain operations cannot be performed at the same working position, by the same turret or by the same spindle head for such evident reasons as tool intersections, impossibility of tool location in spindle head, turret, etc. These exclusion constraints are modeled by undirected graphs G DM =(N,E DM ), G DT =(N,E DT ), and G DP =(N,E DP ), where edge (p,q)E DM ((p,q)E DT ), (p,q)E DP )) if and only if operations p and q cannot be executed by the same machining module, turret, or at the same position, respectively.

The configuration of each machining unit depends on the operations assigned to it. The assignment of operations together, to be executed by the same machining unit, impose additional constraints on the choice of the cutting parameters. The choice of these parameters influences the machining time for each particular part and the makespan for completing all parts.

Let P=<P 1 ,...,P k ,...,P m 0 > is a design decision with P k =( 11 , j=1,2.

Machining time

The execution time t b (P dkjl ) of all operations from N dkjl with a feed per minute

Г dkjl [max{γ 1 (p)|pN dkjl }, min{γ 2 (p)|pN dkjl }] is equal to t b (P dkjl )=L(N dkjl )/Г dkjl + a ,
where L(N dkjl )=max{(p)|pN dkjl }, and  a is an additional constant time for advance and disengagement of tools.

We assume that if a turret of type j is installed at k-th position, then the execution time of all operations from N dkjl is equal to

t h (P dkj )= g b kj +   kj b l 1 t b (P dkjl ), |j=1, 2,
where  g is an additional fixed time for one rotation of turret.

If the spindle head is installed, then t h (P dkj )= t b (P dkjl ), |j=1,2. If all N dkjl are empty, then t h (P dkj )=0.

The execution time t p (P dk ) is defined as

t p (P dk )= r +max{t h (P dkj )|j=1,2},
where  r is an additional constant time for table rotation.

The time T(P) of execution of all corresponding operations after  0 turns of rotary table is defined as follows

T(P)=    0 1 i max{ ) ( ) , ( k k i p P t  |k=1,,m 0 }.
We assume that the objective productivity is provided, if the total time T(P) does not exceed a given available time T 0 . Let C 1 , C 2 , C 3 , and C 4 be the relative costs for one position, one turret, one machining module of a turret, and one horizontal spindle head, respectively.

Since a vertical spindle head (if it presents) is common for several positions, its size (and therefore the cost) depends on the number of positions to be covered. Let h k min and h k max be the minimal and maximal position number for positions covered by a common vertical spindle head. Then, the cost of such a spindle head can be estimated as C 4 +( h k max -h k min )C 5 , where C 5 is the relative cost for covering one additional position by a vertical spindle head.

The cost of a vertical turret can be estimated as C 2 +C 3 b k1 .

In the similar way, the cost C(b k2 ) for performing set of operations N k2 by associated b k2 machining modules can be assessed as follows:

C(b k2 ) =          . 1 if , 1 if , 0 if 0 2 2 3 2 2 4 2 k k k k b b C C b C b
The machine cost Q(P) is calculated as the total cost of all equipment used, i.e.

          ) )( | (| )) | (| 1 |)( (| ) ( 1 3 2 1 12 1 12 1 4 1 0 0 k m k k m k k b C C N sign N sign sign C m C P Q N     0 1 2 min max 5 ) ( ) ( m k k h h b C k k C
where sign(a) = 1 if a > 0, and sign(a) = 0 if a  0.

The studied problem is to determine: a) an orientation for each part to be produced; b) an assignment of operations from set N into subsets N kjl , k=1,...,m 0 , j=1,2, l=1,,b kj to be performed by machining module l of type j at working position k; c) a feed per minute X dkjl employed for each set of operations N dkjl = N kjl N d , d=1,...,d 0 , k=1,...,m 0 , j=1,2, l=1,, b kj in such a way that the machine cost Q(P) is as small as possible and all given constraints are respected.

Based on matrices H(d), d=1, 2, …, d 0 , we can build matrix H of dimension

     0 0 1 1 d d d d d d n r
. N and (p,q)  E SS  E SM  E ST . Each row of H defines in one-to-one manner a partition of N to N 1 and N 2 . Then, the optimal solution of the initial problem can be found as the best partition of corresponding N 1 and N 2 .

In the next section we present MIP formulation of this problem. minimal time necessary for execution of operations p and q by the same machining module, t pq = max((p), (q))/min( 2 (p), 2 (q))+ a

MIP FORMULATION

It is assumed that (p,q)E DM if min(γ 2 (p),γ 2 (q)) < max(γ 1 (p),γ 1 (q)).

Since a vertical spindle head has the common feed rate for all its spindles, it is possible to check the feasibility of installing a common vertical spindle head. It cannot be installed if max{γ 1 (p)|pN 1 } > min{γ 2 (p)|pN 1 }. The vertical turret cannot be installed if there exist operations pN 1 and qN 2 such that (p,q)  E SP or operations pN 1 and qN 1 such that (p,q)  E DT  E DP . If both above cases for spindle head and turret are identified, then the problem has no solution.

The objective function is as follows:

Min              0 0 0 1 2 1 2 4 3 2 1 21 4 1 1 ) 2 ( m k j kj m k k m k k Y C C C Y C Z C ) ( min 1 max 1 5 1 4 1 2 1 3 3 0 0 Y Y C Y C Y C m k j b l kjl          (1)
If an horizontal turret is installed at position k, then Y k21 =Y k22 =1 and

3 2 22 4 3 2 21 4 2 ) 2 ( C C Y C C C Y C k k     
. If an horizontal spindle head is installed at position k, then Y k2l =0, l=2,…,b 0 , and

4 22 4 3 2 21 4 ) 2 ( C Y C C C Y C k k     . If a vertical turret is installed at position k, then Y k11 =Y k12 =1, Y 1 =1, Y 1min =Y 1max and 3 2 min 1 max 1 5 1 4 12 4 3 2 2 ) ( ) 2 ( C C Y Y C Y C Y C C C k       
. If a vertical spindle head is common for positions

k 1 =Y 1min ,,k  =Y 1max , then Y 1 =1, Y k1l =0, l=2,…,b 0 , k=1,…,m 0 and       0 1 4 12 4 3 2 1 4 ) 2 ( m k k C Y C C C Y C .
Variables Z k , k=1,…,m 0 should satisfy the following constraints:

Z k  Y k11 + Y k21 ; k=1,…,m 0 (2) Y k11 + Y k21 2Z k ; k=1,…,m 0 (3)
If N 1 , variables Y 1min and Y 1max can be defined by the following constraints:

(m 0 -k+1)Y k11 +Y 1min  m 0 +1; k=1,…,m 0 (4) Y 1max  kY k11 ; k=1,…,m 0 (5)
The The constraints which prohibit empty machining modules are:

Y kjl-1 ≥ Y kjl ; k=1,…,m 0 ; j=1,2; l=2,…,b 0 (12)
A vertical turret cannot be combined with any other machining module at the same position:

Y k12 +Y k21 1; k=1,…,m 0 (13)
If any vertical turret cannot be installed, then the following equations should be satisfied:

Y k1l =0; k=1,…,m 0 ; l=2,…,b 0 (14)
Otherwise:

Y k11 = Y k12 ; k=1,…,m 0 (14)
Each operation is assigned to one block, this constraints is expressed as follows:

1 0 0 1 1      pkl b l m k X ; pN (15)
If operation p is assigned to l-th machining module of spindle head or turret of type j at k-th position, each operation q, predecessor of p, has to be executed at a previous position or to be assigned to a previous machining module of the corresponding turret:

              0 0 0 0 1 1 0 1 1 0 ) 1 ) 1 (( ) ) 1 (( m k b l qkl m k b l pkl X l b k X l b k ; (p,q)D OR ; p,qN j ; j=1,2 (16)
          0 0 0 0 1 1 1 1 ; ) 1 ( m k b l qkl m k b l pkl X k kX (p,q)D OR ; pN j ; qN 3-j ; j=1,2 (17)
Precedence constraints can be modelled as follows:

qkl l l pkl k k b l l pk X X X           1 1 ' ' 1 1 ' 1 ' ' ' 0 ; (p,q)D OR ; p,qN j ; j=1,2 (17) qkl k k b l l pk X X       1 1 ' 1 ' ' ' 0 ; (p,q)D OR ; pN j ; qN 3-j ; j=1,2 (18) or qkl l l pkl j q Pred p k k b l l pk q Pred p X q Pred X X | ) ( | 1 1 ' ' ) ( 1 1 ' 1 ' ' ' ) ( 0                N ; qN j ; j=1,2 (17)
where Pred(q)={pN|(p,q)D OR }.

For operations p and q that have to be performed at the same working position or by the same turret: For operations p and q that have to be performed by tools of the same machining module or by the same spindle: X pkl X qkl (p,q)E SM E SS ; k=1,…,m 0 ; l=1,…,b 0 (20)

For operations p and q that have to be executed at different working positions: For operations p and q that have to be executed by tools of different turrets, if turrets are used, but can also be executed by the same spindle head:

  0 1 b l pkl X +   0 1 b l qkl X
+Y kj2 2, (p,q) E DT ; p,qN j ; k=1,…,m 0 ; j=1,2 (

For operations p and q that have to be executed by tools of different machining modules:

X pkl X qkl 1(p,q)E DB ; k=1,…,m 0 ; l=1,…,b 0 (23)
The time of execution of operations from N d by l-th machining module of spindle head or turret of type j at k-th position cannot be less than the time of execution of any operation from N d assigned to this machining module: The time of execution of operations from N d at k-th position cannot be less than the time of execution of vertical and horizontal spindle head or turret: The constraint on the throughput is respected if:

d k F  ) 1 ( 2 0 1 3 2 0 0           
i F  ) , ( k i k F  + r ; i=1,…, 0 ; k=1,…,m 0 (28) 0 1 0 T F i i     (
d k F  r d k t    k=1,…,m 0 ; d=1,…,d 0 (37) i F  i T  i T  i=1,…, 0 (38)
where

d t =min{(p)/ 2 (p)+ a + r |pN d } } ,..., 1 | max{ 0 ) , ( m k t T k i i          0 ' , 1 ' ' 0 i i i i i T T T and } ) , ( , ,..., 1 | max{ 0 d k i i T t i d k     
Model (1) -( 38) can be transformed by excluding constraints (20). In this case, family E SSM is created of such subsets e of N that include all operations connected by an edge from E SS or E SM . Then, constraints (15) -( 19) and ( 21) -( 26) are modified by leaving only one operation from each set e E SSM . The efficiency of such a transformation is evaluated in the experimental study presented in Section 5.

AN INDUSTRIAL EXAMPLE

A rotary machine is designed for machining 6 different parts presented in Figures 234567.

Parameters of machining operations are given in Table 1. Operations to be realized for parts 1, 2, 3 and 6 are located on two different sides and all operations for parts 4 and 5 are located on only one side. The sequence of loading parts is {1,2,5,-,3,4,-,6} where "-" means that no part is loaded.

The possible orientations of the parts are defined by the following expressions: H(1)=H( 2

)=H(3)=H(6)=         1 , 2 2 , 1 , H(4)=H(5)=         2 1 .
The total number of possible orientations of all parts is 64=2 6 . Precedence constraints, exclusion constraints for machining modules, turrets and working positions are presented in Tables 2,3, 4 and 5, respectively. Inclusion constraints for positions and machining modules are given in Tables 6 and7. Operations to be executed by the same spindle are presented in Table 8. The total number of feasible orientations of all the parts is reduced to 16 due to constraints from Table 7.

Other parameters of a rotary transfer machine are:  a =  g =  r = 0.1 min. The available time T 0 is 13.2 min.

First, we solve problem (1) -( 38) using academic version of CPLEX 12.2. The obtained optimal solution and its characteristics are presented in Tables 9 and10. The number of variables in the model ( 1) -( 38) is 1224 and the number of constraints is 5521. The solution time was 1.31 sec. The common vertical spindle head cover positions 2 and 3. Only parts 1, 2, 3 are machined at position 1 where a horizontal turret with 4 machining units is installed for machining these parts. Parts 1, 2, 3, 4, 5 are machined at position 2, and all the parts are machined at position 3. There are installed the horizontal turret with 4 machining modules for (parts 1, 2, 3; parts 1, 2, 3; parts 1, 2, 3; part 2) at the position 1 and the horizontal turret with 4 machining modules for part 6 at the position 2. The rotary table turns 1.65 min after the start, then in 2.14 min, 2.1 min, 1.73 min, 1.65 min, 0.24 min, 1.92 min, and in 1.73 min respectively. The total time for machining all parts of the batch is 13.16 min. Then, we solve problem ( 1) -( 38) again with CPLEX 12.2 but by using the reduction of constraints (20) as explained in Section 2. The obtained optimal solution and its characteristics are presented in Tables 11 and12. The number of variables in the model is 828 and the number of constraints is 4824. The solution time was 1.21. There is the vertical spindle head common for positions 2 and 3. Parts 1, 2, 3, 4, 5 are machined at the position 2, and all the parts are machined at the position 3. There are installed the horizontal turret with 4 machining modules (part 6; part 6; part 6; part 6) at the position 1 and the horizontal turret with 4 machining modules (part 2; parts 1, 2, 3; parts 1, 2, 3; parts 1, 2, 3) at the position 2. The rotary table turns 1.65 min after the start, then in 2.14 min, 2.1 min, 1.73 min, 1.65 min, 1.92 min, 0.1 min, and in 1.73 min, respectively. The total time for machining all parts of the batch is 13.02 min. Finally, the summary of the generated models and obtained results for different combinations of constraints ( 20), ( 17) -( 18), (17) -(18), and (17) is presented in Table 13. The locations of parts at the loading position and the general view of the designed rotary transfer machine according to the solution from Table 9 are presented in Fig. 2 and Fig. 3.

EXPERIMENTAL STUDY

The purpose of this study is to evaluate the effectiveness of the proposed optimization approach. Series of 100 test instances for 4, 6 and 8 different parts were generated. Their characteristics are presented in Fig. 10-11 and Tables 141516, where |N| is the number of operations, OSP is the order strength of precedence constraints, DM, DT, DP, SS, and SM are the densities of graphs G DM , G DT , G DP , G SS , and G SM , respectively. The constraints were generated using the techniques and software presented in [START_REF] Dolgui | Optimisation of multi-position machines and transfer lines[END_REF]. Experiments were carried out on ASUS notebook (1.86 Ghz, 4 Gb RAM) with academic version of CPLEX 12.2. First, we compare the results of using model ( 1) -( 38) with different combinations of constraints ( 20), ( 17) -( 18), ( 17) -(18), and (17) for test instances with 4 parts.

By analyzing the results presented in Table 17, we can see the positive impact of the reduction of constraints (20). Then, we compare the effectiveness of modeling precedence constraints by ( 17) -( 18), (17) -( 18) and (17). The summary results are presented in Table 18. Finally, we present in Table 19 the summary results of solving 3 series of 100 test instances for 4, 6, and 8 parts with constraints (17) -( 18) and the transformation of constraints (20). The maximal available time was set up to 2 hours (7200 sec). Feasible solutions were found for all test instances. However, only for 2 instances with 6 parts the optimality of found solutions was not proved while the number of such instances with 8 parts is equal to 11 with maximal gap 34.3 % (see Table 20). Number of solved problems in function of time is depicted in Figure 12. Parameters of easy and hard instances are presented in Table 20 and 21, respectively. 6. CONCLUSION This paper has proposed a joint formulation for process planning and system configuration for design of rotary transfer machines for a mixed-model production of different parts. The objective of suggested models is to minimize the total system cost. A mathematical formulation with several variants for this combinatorial optimization problem was developed and evaluated on an industrial case study. It was shown that the developed models could be successfully applied to the production cases with 6 different types of parts to be machined simultaneously at such a transfer machine. However, since the problem size is substantially increasing when the number of different types of parts is growing, as a consequence, it makes difficult to obtain optimal solutions for larger problem sizes. To address such problems efficiently within reasonable solution time, approximate methods have to be developed. Having such methods available will also allow envisaging the extension of the optimization problem by considering the sequence of the parts to be determined at the same time as the process planning and the system configuration.

  |N j N d | d kjl Y ; d=1,…,d 0 ; k=1,…,m 0 ; j=1,2; l=1,…,b 0

  of type j with b kj machining modules is installed at k-th position, least one operation from N d is executed by the turret and d k F =0, otherwise. If a spindle head of type j is installed at k-th position, then d k F  d kj F 1 .

Fig. 2 .Fig. 4 .Fig. 6 .

 246 Fig.2. The first part to be machined

Fig. 10

 10 Fig. 10 Characteristics of test instances (number of operations)

  Part d can be located in different orientations, the set of all possible orientations is H(d) is known. Part orientation is done at zero position and still the same for all working positions. Elements of no more than one side can be machined by vertical spindle head or turret. All elements of other sides of the part have to be assigned to horizontal spindle heads or turrets. H(d) can be represented by matrix of dimension r d xn d where h rs (d) is equal j, j=1,2 if the elements of the s-th side of the part d can be machined by spindle head or turret type j.

	side of the part. Let N=  0 d N d . All operations pN are characterized by the following parameters:
	1 d 
	-length (p) of the working stroke for operation pN, i.e. the distance to be run by the tool in order to
	complete operation p;
	-range [γ 1 (p), γ 2 (p)] of feasible values of feed rate which characterizes the machining speed;
	-set H(p) of feasible orientations of the part (indexes r{1, 2, …, r d } of rows of matrix H(d)) for
	execution of operation p d s N by spindle head or turret of type j (vertical if h rs (d)=1 and horizontal if
	h rs (d)=2).
		Common vertical
		multi-spindle head
	Turret	Turret
		Horizontal multi-
		spindle head

  Let us introduce the following notations: X pkl decision variable which is equal to 1 if operation p from N is assigned to l-th machining module of spindle head or turret of type j at k-th position (j=1 if pN 1 and j=2 if pN 2 )

	d kjl d kj Y kjl Y Y kjl F d k F F i Y d t pq	auxiliary variable which is equal to 1 if at least one operation for machining elements of d-th part is executed in l-th machining module of spindle head or turret type j at k-th position ( d kjl Y =0 if N j =) auxiliary variable which is equal to 1 if at least one operation for machining elements of d-th part is executed by a spindle head or turret of type j at k-th position ( d kj Y =0 if N j =) auxiliary variable which is equal to 1 if l-th machining module of spindle head or turret of type j is installed at k-th position auxiliary variable for determining the time of execution for operations from N d by l-th machining module of spindle head or turret of type j at k-th position auxiliary variable for determining the time of execution of operations from N d at k-th position auxiliary variable for determining the time of execution of all operations from N when machining of part  i is finished

1min auxiliary variable which is equal to k if k is the first position covered by a vertical spindle head or turret (Y 1min =0 if N 1 =) Y 1max auxiliary variable which is equal to k if k is the last position covered by a vertical spindle head or turret (Y 1max =0 if N 1 =) Z k auxiliary variable which is equal to 1 if at least one operation is assigned to k-th position

Table 1 .

 1 Operations and their parameters

		γ 1 (p),	γ 2 (p),
	mm	mm/min	mm/m
			in

p Hole Part Side (p), mm γ 1 (p), mm/min γ 2 (p), mm/min p Hole Part Side (p),

Table 2 .

 2 Precedence constraints

	Operation	Predecessors	Operation	Predecessors
	2	1 3 29 31	40	9 11 13 15 37 39 41 43
	4	1 3 29 31	42	9 11 13 15 37 39 41 43
	6	5 7 33 35	44	9 11 13 15 37 39 41 43
	8	5 7 33 35	50	49 51
	10	9 11 13 15 37 39 41 43	52	14 42 49 51 64
	12	9 11 13 15 37 39 41 43	54	53 55 59
	14	9 11 13 15 37 39 41 43	56	53 55 59
	16	9 11 13 15 37 39 41 43	58	57
	30	1 3 29 31	60	53 55 59
	32	1 3 29 31	62	61
	34	5 7 33 35	63	62
	36	5 7 33 35	64	63
	38	9 11 13 15 37 39 41 43

Table 7 .

 7 Operations to be assigned to the same machining module

	Operation Operations to be executed by the same machining module	Operation	Operations to be executed by the same machining module
	1	3	33	35
	5	7	34	36
	6	8	37	39 41 43
	9	11 13 15	49	51
	17	19	53	55 59
	18	20	54	56 60
	29

Table 8 .

 8 Operations to be executed by the same spindle

	Operation Operations to be executed by the same tool	Operation	Operations to be executed by the same tool
	1	29	11	39
	2	30	12	40
	3	31	13	41
	4	32	14	42
	5	33	15	43
	6	34	16	44
	7	35	21	45
	8	36	22	46
	9	37	23	47
	10	38	24	48

Table 9

 9

	. An optimal solution
	Set N dkjl	Operations of N dkjl L(N dkjl ) γ dkjl	t b (P dkjl )
	N 1121	9 11 13 15	24	83.6	0.39
	N 2121	26	2	62.7	0.13
	N 3121	37 39 41 43	24	83.6	0.39
	N 1122	10 14 18 20	25	82.2	0.4
	N 2122	27	2	62.7	0.13
	N 3122	38 42	9	106.3	0.18
	N 1123	12 16 17 19	25	82.2	0.4
	N 2123	28	2	62.7	0.13
	N 3123	40 44	9	106.3	0.18
	N 2124	25	2	62.7	0.13
	N 1211	1 3 5 7	79	51.6	1.63
	N 2211	22 23	2	51.6	0.14
	N 3211	29 31 33 35	79	51.6	1.63
	N 4211	46 47	2	51.6	0.14
	N 5211	49 51 53 55 57 59	100	51.6	2.04
	N 6221	61	40	74.1	0.64
	N 6222	62	24	197.1	0.22
	N 6223	63	24	161.6	0.25
	N 6224	64	18	160.2	0.21
	N 1311	2 4 6 8	75	51.6	1.55
	N 2311	21 24	2	51.6	0.14

Table 11

 11

	. An optimal solution
	Set N dkjl	Operations of N dkjl L(N dkjl ) γ dkjl	t b (P dkjl )
	N 6121	61	40	74.1	0.64
	N 6122	62	24	197.1	0.22
	N 6123	63	24	161.6	0.25
	N 6124	64	18	160.2	0.21
	N 1211	1 3 5 7	79	51.6	1.63
	N 2211	22 23	2	51.6	0.14
	N 3211	29 31 33 35	79	51.6	1.63
	N 4211	46 47	2	51.6	0.14
	N 5211	49 51 53 55 59 57	100	51.6	2.04
	N 2221	28	2	62.7	0.13
	N 1222	9 11 13 15	24	83.6	0.39
	N 2222	26	2	62.7	0.13
	N 3222	37 39 41 43	24	83.6	0.39
	N 1223	12 16 17 19	25	82.2	0.4
	N 2223	25	2	62.7	0.13
	N 3223	40 44	9	106.3	0.18
	N 1224	10 14 18 20	25	82.2	0.4
	N 2224	27	2	62.7	0.13
	N 3224	38 42	9	106.3	0.18
	N 1311	2 4 6 8	75	51.6	1.55
	N 2311	21 24	2	51.6	0.14
	N 3311	30 32 34 36	75	51.6	1.55
	N 4311	45 48	2	51.6	0.14
	N 5311	50 52 54 56 60 58	98	51.6	2.0
	N 6311	65 66 67 68 69 70	3	51.6	0.16

Table 13 .

 13 Characteristics of the models

	Constraints	Precedence	Number of	Number of	Time solution
	(20)	constraints	variables	constraints	(sec)
		(17) -(18) 1224	5521	1.314
	Yes	(17) -(18) 1224	6797	1.571
		(17)	1224	5741	1.575
		(17) -(18) 828	4824	1.207
	No	(17) -(18) 828	5000	1.226
		(17)	828	4940	1.295

Table 14

 14

	Test series with 4 parts
	Parameters of problems	|N| OSP	DM	DT	DP	SS	SM	LS
	Minimal value	44 0.034 0.064 0.026 0	0.027 0	4
	Maximal value	95 0.161 0.659 0.659 0.242 0.051 0.016 8
	Average value	69 0.102 0.373 0.348 0.023 0.036 0.004 6

Table 15

 15

	Test series with 6 parts
	Parameters of problems	|N| OSP	DM	DT	DP	SS	SM	LS
	Minimal value	89 0.029 0.003 0.002 0	0.024 0	6
	Maximal value	159 0.111 0.462 0.462 0.205 0.031 0.008 9
	Average value	124 0.08	0.229 0.198 0.028 0.027 0.002 7
	Table 16 Test series with 8 parts
	Parameters of problems	|N| OSP	DM	DT	DP	SS	SM	LS
	Minimal value	118 0.023 0.004 0.004 0	0.024 0	8
	Maximal value	216 0.083 0.526 0.525 0.214 0.033 0.006 12
	Average value	166 0.055 0.297 0.266 0.027 0.028 0.002 10

Table 17

 17

	Impact of the transformation of constraints (20) on test series with 4 parts
	Parameters	With inclusion	With reducing inclusion
		constraints (20)	constraints (20)
	Minimal time (sec)	1.32	0.76
	Maximal time (sec)	601.074	609.27
	Average time (sec)	38.238	33.912
	Total time (sec)	3823.81	3391.17
	Number of instances	86	14
	solved in shorter time

Table 18

 18

	Impact of modeling precedence constraints
	Parameters	(17) -(18)	(17) -(18)	(17)
	Minimal time (sec)	0.76	1.071	0.665
	Maximal time (sec)	609.27	544.771	3790.99
	Average time (sec)	33.912	46.19	140.405
	Total time (sec)	3391.17	4619.01	14040.5
	Number of instances	69	13	18
	solved in shorter time

Table 19

 19

	Time solution of test instances
	Parameters		4 parts		6 parts	8 parts
	Minimal time (sec)	0.76		0.678		1.693
	Maximal time (sec)	609.27		7200		7200
	Average time (sec)	33.912		703.742	1767.59
	Total time (sec)		3391.17	70374.2	174992
	Number of solved	100		100		100
	instances
	Number of instances	100		98		89
	with proven optimality
	Table 20 Parameters of easy test instances
	Parameters of	|N|	OSP	DM	DT	DP	SS		SM	LS	Time,
	problems										sec
	4 parts	63	0.093	0.598 0.591 0.001 0.037	0.002 4	0.76
	6 parts	106 0.086	0.024 0.014 0.009 0.030	0.003 6	0.68
	8 parts	159 0.065	0.162 0.161 0.000 0.024	0.000 8	1.69
	Table 21 Parameters of hard test instances
	Parameters of	|N|	OSP	DM	DT	DP	SS	SM	Time,	LS	Gap,
	problems								sec		%
	4 parts	69	0.104 0.249 0.141 0.100 0.033 0.00 609.3 8	0
	6 parts	118 0.094 0.335 0.291 0.037 0.028 0.000 7200 8	4.91
	6 parts	159 0.065 0.335 0.291 0.037 0.028 0.000 7200 8	6.3
	8 parts	176 0.061 0.291 0.276 0.009 0.027 0.001 7200 8	15.8
	8 parts	148 0.043 0.232 0.155 0.062 0.031 0.001 7200 8	2.3
	8 parts	185 0.079 0.264 0.226 0.026 0.026 0.000 7200 8	34.3
	8 parts	185 0.079 0.260 0.220 0.032 0.026 0.001 7200 8	22.5
	8 parts	175 0.073 0.277 0.220 0.046 0.028 0.001 7200 8	8.1
	8 parts	177 0.073 0.230 0.221 0.006 0.025 0.002 7200 8	4.4
	8 parts	170 0.072 0.185 0.169 0.010 0.027 0.001 7200 8	25.2
	8 parts	132 0.053 0.316 0.254 0.046 0.032 0.001 7200 8	19.1
	8 parts	180 0.060 0.219 0.046 0.168 0.028 0.000 7200 8	14.5
	8 parts	179 0.060 0.378 0.295 0.075 0.026 0.000 7200 8	7.0

 Battaïa, O., Dolgui, A., Guschinsky, N., and Levin, G. (2012a). A decision support system for design of mass production machining lines composed of stations with rotary or mobile table. Robotics and Computer-Integrated Manufacturing, 28, 672-680. Battaïa, O., Dolgui, A., Guschinsky, N., and Levin, G. (2012b). Optimal design of machines processing pipeline parts. International Journal of Advanced Manufacturing Technology, 63, 963-973.