Maxime Gonthier
email: maxime.gonthier@ens-lyon.fr

Loris Marchal
email: loris.marchal@ens-lyon.fr

Samuel Thibault
email: samuel.thibault@u-bordeaux.fr

A generic scheduler to foster data locality for GPU and out-of-core task-based applications

Hardware accelerators, such as GPUs, now provide a large part of the computational power used for scientific simulations. GPUs come with their own (limited) memory and are connected to the main memory of the machine via a bus with limited bandwidth. Scientific simulations often operate on very large data, to the point of not fitting in the limited GPU memory. In this case, one has to turn to out-of-core computing: data are kept in the CPU memory, and moved back and forth to the GPU memory when needed for the computation. This out-of-core situation also happens when processing on multicore CPUs with limited memory huge datasets stored on disk. In both cases, data movement quickly becomes a performance bottleneck.

Task-based runtime schedulers have emerged as a convenient and efficient way to manage large applications on such heterogeneous platforms. They are in charge of choosing which tasks to assign on which processing unit and in which order they should be processed.

In this work, we focus on this problem of scheduling for a taskbased runtime to improve data locality in an out-of-core setting, in order to reduce data movements. We design a data-aware strategy for both task scheduling and data eviction from limited memories. We compare this to existing scheduling techniques in runtime systems. Using the StarPU runtime, we show that our strategy achieves significantly better performance when scheduling tasks on multiple GPUs with limited memory, as well as on multiple CPU cores with limited main memory.

increasing parallelism, with large multicore processors and hardware accelerators such as GPUs. However, recent technology trends show a widening gap between peak compute speed and communication bandwidth as well as decrease in memory per gigaflop [START_REF] Cheng | Chapter 20 -Optical interconnection networks for high-performance systems[END_REF][START_REF] Council | Getting up to speed: The future of supercomputing[END_REF]. With users trying to solve larger systems, it becomes common to encounter a situation where all input data of the problem cannot fit into the memory of the computing units (either CPUs or GPUs).

To avoid running out of memory, out-of-core computing has emerged, allowing the input data to stay on slow but large storage (typically disk) and to be loaded into the memory of the processing units (typically CPUs) whenever needed for the computation [START_REF] Agullo | A parallel out-of-core multifrontal method: Storage of factors on disk and analysis of models for an out-of-core active memory[END_REF]. All cores of a multicore CPU share a common (limited) memory, as depicted on Figure 1. The bandwidth between the disk and the CPU memory is only of a few hundred MB/s, which has a strong impact on performance if data movements are not carefully handled to overlap them with computation. Similarly, one should avoid loading several times the same data but favor data reuse, by improving temporal data locality, i.e., by performing all computations on the same data before its eviction from the memory.

Recently, the trend has been to leverage GPUs in addition to CPUs, to achieve unforeseen computation speed as well as energy requirements efficiency. GPU can achieve multiple teraflops in performances but are limited by a shared bandwidth of a few thousands MB/s. In this case, out-of-core computing consists in keeping the whole input data in the (larger) memory of the CPU, and loading data in the memory of a GPU only when it is needed for computation (see Figure 2). In such a distributed memory context, data reuse is even more crucial as one has also to focus on spatial data locality, that is to aim at gathering all computations on the same data on the same GPU. Hence, the gap between communication speed and computation is a strong performance bottleneck when computing on large data.

In this paper, we consider that these these two out-of-core situations (multicore CPU with limited shared memory and GPUs with limited distributed memory) can be treated similarly, and we focus on any system with two levels of memory: one fast and limited memory devoted to computations (in red in Figures 1 and2), and one large but slower memory devoted to storing the whole dataset (in green in Figures 1 and2).

To harness the power of complex heterogeneous computing platforms, it has become very common to use task-based programming, i.e. to express the application computation as a Directed Acyclic Graph (DAG), and let a dynamic runtime system such as OmpSs [START_REF] Bueno | Productive programming of GPU clusters with OmpSs[END_REF], PaRSEC [START_REF] Bosilca | PaRSEC: A programming paradigm exploiting heterogeneity for enhancing scalability[END_REF], or StarPU [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] manage the execution of the task graph over such distributed and heterogeneous platforms. The burden of allocating data in memory, choosing task processing order and mapping is thus offloaded from the application programmer to the runtime system, in the form of a task scheduling problem. As the runtime system handles both data and tasks, it has the opportunity to minimize data movement. The runtime scheduler must solve the complex task of deciding the mapping of the tasks to the processing units to improve spatial data locality, as well as the ordering of the tasks itself, to privilege the temporal locality of data, thus favoring data reuse and saving duplicate data transfers. In addition, this scheduler has to account for task priorities (some tasks may be more crucial to compute early than others) and task affinities (in case of a heterogeneous platform, some tasks have a larger acceleration factor on GPUs than others). Besides, it is also essential to trigger data transfers ahead of task execution (data prefetches) so that they can be overlapped by the computation of the previous tasks. Last but not least, when the embedded memory of the processing unit is full, the runtime has to carefully decide which data should be evicted from it, to make room for further data.

In this paper, our aim is to solve this challenging problem, that is we propose a task scheduler for runtime systems managing several computing units with shared or distributed limited memory. We also aim at managing data movements (loads and evictions). More precisely, we want to determine (i) the assignment of the tasks to the processing units to reach a good load balance and spatial data locality and (ii) the order in which tasks must be processed on each processing unit to optimize temporal data locality as well as maximize overlap between computations and data movements. Our solution is data-centric, trying to re-use data as much as possible: a processing unit is assigned all the "free" tasks, for which it already owns all input data. Then, when no more free tasks can be performed on a processing unit, we look for the data that, if transferred to its memory, would allow to assign many tasks on this processing unit, for a minimal transfer time. Our scheduling strategy also looks for a good trade-off between data locality and priority in the task graph. Finally, we design a custom eviction policy that takes advantage of the (limited) vision of tasks to be processed on a processing unit to avoid evicting data that will be useful in a near future.

In this paper, we make the following contributions:

• We review existing schedulers in task-based runtime systems. • We propose DARTS, a Data-Aware Reactive Tasck Scheduler for out-of-core computing in task-based runtime systems with a custom eviction policy; • We implemented DARTS within the StarPU runtime system; • We compare the performance of DARTS and existing schedulers on two classical linear-algebra benchmarks (namely Cholesky and LU factorization), on two out-of-core settings: (i) multiple GPUs with distributed memory and (ii) a multicore CPU with shared memory. • Our experiments demonstrate that our scheduler is able to achieve good performance even when the memory is very limited, whereas all existing schedulers see their performance drop. Besides, DARTS performs comparably to the best existing schedulers when memory is not limited.

Note that the present paper extends a previous version of DARTS [START_REF]Authors removed for double-blind submission, A. Memory-Aware Scheduling of Tasks Sharing Data on Multiple GPUs with Dynamic Runtime Systems[END_REF]. The previous version was limited to independent tasks sharing data, hence it was unable to handle complete task graphs as required by runtime systems, and was only tested on restricted task sets.

The rest of this paper is organized as follows. Section 2 presents previous work in the area. Section 3 details the scheduling problem in runtime systems. Section 4 shows existing schedulers for runtime systems, and our scheduler is presented in Section 5. Section 6 presents the experiments to test our scheduler both on multiple GPUs and on CPU.

RELATED WORK

We review here existing work both on specific out-of-core algorithms and on scheduling for runtime systems.

Out-of-core algorithms. Out-of-core computation has been proposed to process large datasets for specific operations, mainly in linear algebra. Toledo [START_REF] Toledo | A survey of out-of-core algorithms in numerical linear algebra[END_REF] surveys such out-of-core for dense linear algebra operations. This appears also in sparse linear algebra: Demmel et al. [START_REF] Demmel | Avoiding communication in sparse matrix computations[END_REF] propose to reduce the amount of data transfers both between processing elements and from/to the main memory. Direct sparse solvers are known to produce large amount of temporary data, which makes out-of-core computing the only solution to factorize very large sparse matrices [START_REF] Agullo | A parallel out-of-core multifrontal method: Storage of factors on disk and analysis of models for an out-of-core active memory[END_REF]. Marchal et al. [21] also focus on reducing data transfers for task trees arising in sparse direct solvers. Such algorithms are however tailored to specific application cases, while task-based runtime systems aim for generic-purpose designs.

Scheduling and data locality in runtime systems. As outlined in the introduction, runtime systems like OmpSs [START_REF] Bueno | Productive programming of GPU clusters with OmpSs[END_REF], PaRSEC [START_REF] Bosilca | PaRSEC: A programming paradigm exploiting heterogeneity for enhancing scalability[END_REF], or StarPU [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] are increasingly popular to cope with the complexity of modern computing platforms. In this context, some runtimes have been striving to improve data locality for better performance. Many runtime systems such as XKaapi [START_REF] Ferreira Lima | Design and analysis of scheduling strategies for multi-CPU and multi-GPU architectures[END_REF] rely on work-stealing for load balancing, which also gives some guarantee on data locality [START_REF] Acar | The data locality of work stealing[END_REF]. On the contrary, the StarPU runtime system automatically calibrates performance models to predict task execution times. Based on these predictions, the DMDAS scheduler (presented below in Section 4.2) schedules tasks on the resource on which they are expected to complete at the earliest, which also takes data transfers into account. These predictions, however, only rely on the current state of the memory, and do not take into account its limited size: when some new data are loaded in memory, other data may be evicted, which is not taken into account and may lead to incorrect predictions. Legion [START_REF] Bauer | Legion: Expressing locality and independence with logical regions[END_REF] allows the user to express locality thanks to data regions, and to provide a data mapping strategy to ensure that data is not moved around when it is not necessary.

For the specific case of computing matrix products on multiple GPUs, the PaRSEC runtime pays attention to the memory limitation and implements a control-flow in order to avoid critically overflowing the GPUs' memory [START_REF] Herault | Generic Matrix Multiplication for Multi-GPU Accelerated Distributed-Memory Platforms over PaRSEC[END_REF].

Hence, no existing runtime system is able to automatically deal with both data locality and limited memory for general computations.

PROBLEM STATEMENT

We present here the model of the computing platform used when presenting the algorithms below, and we precisely state the objectives of a memory-aware scheduler for a runtime system.

Computing platform model

We concentrate in this paper on two different memory-limited architectures, namely a shared limited memory (Figure 1) and a distributed limited memory (Figure 2). We consider that the sharedmemory setting is a special case of the distributed setting, as it includes a single memory, used by multiple cores which can be viewed as a single more efficient, parallel processing element. Hence, we concentrate the description of the problem and the algorithms on the more general distributed case, where the processing units are the GPUs and the large and slow storage is the main memory of the CPU. However, the problem and proposed algorithms can be easily translated for the shared memory case, as in the experiments reported in Section 6.4. Each of the GPUs have their own memory with the same limited size M. They are all connected to the main memory of the machine through a shared communication link (PCI Express bus) whose bounded bandwidth is shared by all the communications taking place simultaneously between the main memory and some GPUs. All input data originally reside on the main memory, whose size is assumed sufficient to store all the original and temporary data of the computation.

Note that in addition to the PCI Express bus connecting all GPUs to the main memory, direct and faster connections may be available on some pairs of GPUs (such as NVidia NVLink or NVSwitch). This may allow to load data in a GPU faster than from the main memory if the data is already on another GPU.

Task-based runtime scheduler

The application is described by the programmer as a task graph, where vertices represent tasks and edges represent data dependencies between tasks. The programmer provides the code for each task as well as the description of its input and output data, allowing the runtime system to assign tasks to processing units and to move data around when needed. Figure 3 provides a small example of such a task graph. At a given time of the computation, some of the tasks have been completed, and some tasks are not available for computation as their input data has not been computed yet (tasks with pale colors on Figure 3). The tasks available for computation, i.e.

, not yet processed but with all their predecessors completed, form a subset of independant tasks in the graph, called the ready tasks (bright tasks in the figure). Several of these available tasks depend on common predecessors (e.g., both GEMM_3_1_0 and GEMM_3_2_0 depend on the result of TRSM_3_0), which means that they share a common input data produced by the common predecessor. The runtime scheduler has the knowledge of this dependency pattern and can take advantage of this to improve data locality while mapping and scheduling tasks (e.g., by mapping GEMM_3_1_0 and GEMM_3_2_0 to the same GPU). We denote by D(T ) the input data of task T . Data may have different sizes, and tasks may have different processing times: this information is available to the scheduler through profiling.

The runtime system takes care of prefetching (loading a data a bit earlier so as to avoid waiting for unavailable data), marking tasks as available when their predecessors complete and managing task queues. The scheduler has the responsibility to map and order task on each processing unit. Given a set of ready tasks, when a processing unit is idling, the scheduler must send a task to this processing unit. If a processing unit needs to load a data in order to compute a task and the memory is saturated, the scheduler has to evict a data from the processing unit's memory.

In this paper, we are focusing on optimizing the scheduler for data locality, hence we propose algorithms to map tasks to processing units, order tasks on each processing unit and evict data from the limited memory when needed.

In a previous study, we proved that the simpler problem of ordering tasks sharing input data to minimize data movement on a single processing unit was NP-complete [START_REF]A. Locality-Aware Scheduling of Independent Tasks for Runtime Systems[END_REF], hence the more general problem studied in the present paper is also NP-complete.

Note that we concentrate here only on tasks' input data: in the case of linear algebra for instance, the output data of task is most often smaller than the input data and can be transferred concurrently with data input. Data output is then not the driving constraint for efficient execution, as our experiments show. Our model could however be extended to integrate large task outputs if needed.

EXISTING RUNTIME SCHEDULERS

In this section, we present various algorithmic solutions that already exist in the literature to solve the partitioning and scheduling problem presented above. Some of these methods are greedy (Section 4.1), some first solve the partitioning problem, and then schedule the tasks on each processing unit (Section 4.2), some use work stealing to deal with load balancing and locality (Section 4.3), and some uses priority as a main focus point (Section 4.4).

The baseline: EAGER

The EAGER scheduler allows processing units (PUs) to pick up tasks on demand from a shared queue. The queue is filled with tasks as they get released by dependencies. Hence, task are processed in the order of their release.

Dynamic scheduler of StarPU: DMDAS

DMDA or "Deque Model Data Aware" (Algorithm 1) is a dynamic scheduling heuristic designed to schedule tasks on heterogeneous processing units in the StarPU runtime [START_REF] Augonnet | Data-Aware Task Scheduling on Multi-Accelerator based Platforms[END_REF] (also called tmdp-pr). It computes for each processing unit PU k the expected completion time C(T i , PU k ) of the first task T i in the queue of ready tasks, based on a prediction of the time required to transfer the data to the processing unit (comm) and of the task computation time (comp):

C(T i , PU k ) = D j ∈ D(T i ) D j memory(PU k ) comm(D j , PU k )+comp(T i , PU k ) (1)
Note that the data transfer time is counted only if the data is not already in the memory of the processing unit. The task is then assigned to the processing unit PU k which minimizes C(T i , PU k ). Communication and computation times are predicted using a performance profile of the communication bus and processing unit which is calibrated beforehand. Tasks are assigned to processing units with this rule, one by one in the order of their release by the completion of their input dependencies.

DMDAS is a variant of DMDA that sorts tasks in the queue by priority order (as provided by the application). It is the default stateof-the-art scheduler used by the Chameleon library [START_REF] Agullo | Achieving high performance on supercomputers with a sequential task-based programming model[END_REF]. DMDAS also includes an additional Ready strategy (Algorithm 2): tasks are reordered at runtime in order to favor tasks with the most input data already loaded into memory 1 .

Algorithm 1 Deque Model Data Aware heuristic (DMDA) 1: InMem ← ∅ 2: while not all ready tasks have been assigned do 3:

T i ← pop(readyTasks) 4:
Compute C(T i , PU k ) using Eq. 1 for each PU k 5:

Assign T i to PU k with smallest C(T i , PU k ) 6:
for each D j ∈ D(T i ) do 7:

Request data prefetch for D j in PU k Wait for all data in D(T ) to be in PU's memory 4:

Start processing T

In contrast to EAGER, DMDAS is a more advanced policy in terms of scheduling. It provides optimized execution thanks to its Ready strategy coupled with the DMDA algorithm and task priorities.

A work stealing policy: LWS

Locality Work Stealing (or LWS) is a scheduler that combines work stealing for load balancing, and locality to minimize communication.

Each worker has a queue of tasks planned for future execution. LWS can deal with locality in two ways. First, when a task is released, it is queued on the worker that released it. Thus, by default a task and its descendants are all scheduled on the same worker. In most cases, the descendants of a task all share at least one input data, so scheduling them on the same worker favors data reuse. Secondly, when a worker becomes idle, it steals a set of tasks from neighboring workers. It steals tasks from the end of their queue. There is a high chance that the inputs of these tasks have not been prefetched yet. This encourages workers to work on different input data. It thus favors distribution of different data to different workers, which increases the locality within each worker's task queue.

Work Stealing has proven to be efficient in situations where partitioning and reducing communication is critical (see [START_REF] Quintin | Hierarchical work-stealing[END_REF], LWS is similar to HWS).

A priority-based scheduler from the PaRSEC runtime

DPLASMA [START_REF] Bosilca | Flexible development of dense linear algebra algorithms on massively parallel architectures with DPLASMA[END_REF] is a well-known implementation of dense linear algebra operations for heterogeneous architectures. It uses PaR-SEC [START_REF] Bosilca | PaRSEC: A programming paradigm exploiting heterogeneity for enhancing scalability[END_REF], a dynamic runtime for architecture-aware scheduling of tasks on heterogeneous architectures. PaRSEC comes with different schedulers that all share two common aspects. First, they use the theoretical performance of CPUs and GPUs to balance the load assigned to each processing unit. Second, they use the knowledge of the DAG [START_REF] Moustafa | sweep for massively parallel architectures with PARSEC[END_REF] to evaluate the cost of a task relative to its input, i.e. if multiple tasks use the same input data, the cost of a task will only be its computation time (without counting the data loading time) as its input data can be reused. Thus, multiple tasks that share input data have a higher probability of being computed on the same processing unit.

In our experiments, we use the Absolute Priority scheduler (AP) because of it affinities with priorities, an important feature for the applications we will be using. With AP, all processing units share a task waiting queue that is sorted by priority, and every time a processing unit becomes available, it takes for execution a task from the head of the waiting queue. We also evaluated the default scheduler of PaRSEC: LFQ. We found that AP always get slightly better performance on our applications. For this reason we only show AP in the following experiments.

PROPOSED STRATEGY FOR OUT-OF-CORE SITUATIONS: DARTS

We present here our main contribution, the DARTS scheduler (for Data-Aware Reactive Task Scheduling). A preliminary version of DARTS limited to tasks without dependencies has already been proposed [START_REF]Authors removed for double-blind submission, A. Memory-Aware Scheduling of Tasks Sharing Data on Multiple GPUs with Dynamic Runtime Systems[END_REF]. For completeness, we outline here the whole scheduler, but we detail the new features.

Intuition

The principle of DARTS is to consider data locality before task assignation. The scheduling decision is based on the data (the data already loaded into the memory of the processing units and the data used by the ready tasks) and an ordered list of tasks is derived from it. The goal is to perform as many tasks as possible with the data available in the processing unit. Strategies presented in the previous section were favoring priority over locality: DMDAS and AP sort tasks by priority, favoring progress on the task graph critical path over data reuse. On the contrary, DARTS can contradict priority when useful to favor data reuse.

Task flow

In order to grasp DARTS' strategy, we need to understand the flow of tasks within the StarPU runtime as described in Figure 4. This figure uses the distributed memory case with GPUs because it is the more complete case, but the behavior is similar for shared memory with CPUs. The pink box represents the common StarPU core, and the boxes above it represent the specific scheduler, here DARTS. Tasks ready for execution are provided to DARTS through the readyTasks queue. When a GPU k is idling, it will pull the head of the taskBuffer k queue of tasks. If that is empty, it will pull tasks from plannedTasks k . And if that is empty, DARTS will be called to fill plannedTasks k using tasks from readyTasks. Note that tasks in taskBuffer k are in the StarPU common core and their data are being prefetched into the GPU memory. Thus, DARTS cannot access those tasks anymore. However, tasks in plannedTasks k can still

Strategy

DARTS is detailed in Algorithm 3. PU k denotes the k-th processing unit. The principle of DARTS is, when requested for tasks to put in plannedTasks k for PU k , to first look for the best new data to load, that is, a data that will allow as much work to be performed on PU k as possible. Our first improvement over the previous DARTS design [START_REF]Authors removed for double-blind submission, A. Memory-Aware Scheduling of Tasks Sharing Data on Multiple GPUs with Dynamic Runtime Systems[END_REF] comes from the selection of the best data to load. Whenever some PU k requests for some task to execute, we first look in the dataNotInMem k set (which initially contains all data) for the optimal data D opt that, if moved into the memory of PU k , would minimize the ratio between the transfer duration of D opt and the computation time of tasks that become "free", i.e., tasks that can be assigned and processed on PU k without any additional data movement. Considering the transfer duration allows to favor direct communication between GPUs (using NVLinks), which is much faster than using the PCI Express bus. In case of equality between several optimal data, we break ties by considering task priorities and the remaining work associated with a data. Once such data is found, all the corresponding free tasks are assigned to plannedTasks k . If we cannot find a data which enables free tasks, we then look for the data D opt that will enable a high-priority task T provided that we perform one more data transfer: T depends on D opt , on another data D not in memory, and possibly other data already in memory.

It may happen that we do not find any such data, for example if all ready tasks depend on at least three data not in memory. In this case, the highest-priority task from readyTasks is assigned to PU k . We describe here the values required to select the optimal data D opt (see Algorithm 3):

• S 0 (D): the set of tasks that depend only on D and some data already loaded in the memory of PU k . The previous DARTS design only supported independent tasks. The support of task graphs with dependencies requires supporting the dynamic addition of tasks in readyTasks when their dependencies are resolved. When such addition occurs, we dynamically update each dataNotInMem k , to include data used by this new ready task but which was not used by any other ready task, and not loaded or planned for load on PU k . The dataNotInMem k sets thus always contain exactly the set of data used by tasks that can be started (either in readyTasks, in some plannedTasks k , or in some taskBuffer k ), which are not yet loaded on PU k .

Besides, for some newly-released ready tasks, we can bypass readyTasks and directly push them to plannedTasks k when they are already "free". Indeed, since the scheduler controls the loading of data, when a new task becomes ready we can check if it is already free on PU k , i.e., if it can be already be processed by some PU k without any additional data load. In such a case, we directly assign the new ready task to the corresponding plannedTasks k . If several PUs qualify, we first consider the one with the fewest-queued tasks, to balance the load.

Eviction policy

In order to perform under memory constraints, DARTS needs a custom eviction policy, that matches its strategy. The goal is to keep "free" tasks in taskBuffer and plannedTasks so as not to contradict the task order. The eviction policy considers all data currently in memory, and first tries to evict data that is not useful for any task in taskBuffer k (as those tasks are close to being executed on PU k ), and which is an input of few tasks in plannedTasks k . If this is not possible, we apply Belady's rule [START_REF] Belady | A study of replacement algorithms for a virtual-storage computer[END_REF]: evict the input data whose next usage in taskBuffer k is the furthest in the future.

We have updated this eviction policy to update dataNotInMem k for each PU k after the eviction. This is essential for tasksets with dependencies, as the dataset must be dynamically managed to reduce the computational complexity of finding D opt . If the evicted data is not used by any task in readyTasks, we remove it from all dataNotInMem k . It will be added there again when a new ready task with this input becomes available. Otherwise, if any task of readyTasks uses the evicted data, we add it to dataNotInMem k for each PU k that does not hold it in memory (and is not scheduled to load it). This keeps dataNotInMem k up to date with the data that is currently required by ready tasks.

EXPERIMENTAL EVALUATION

We present below the experimental evaluation conducted to compare the strategies presented above. 2 The paper presenting the preliminary version of DARTS [START_REF]Authors removed for double-blind submission, A. Memory-Aware Scheduling of Tasks Sharing Data on Multiple GPUs with Dynamic Runtime Systems[END_REF] only evaluated it on independent tasks, namely variants of the Matrix Multiplication. Our study is more in-depth and takes into account more complex applications, equipped with dependencies.

Settings

All strategies mentioned above have been implemented in the StarPU runtime system [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF], and evaluated both in distributed and shared memory (see details below). We have most often limited the processing units memory to 2000 MB in order to better distinguish the performance of different strategies even on small datasets. All schedulers use the LRU eviction policy except for DARTS. The various schedulers have been tested on two linear algebra applications: the Cholesky decomposition (A = L × L T ) and the LU factorization (A = L × U ) without pivoting. When the scheduler requires task priorities (which is the case for DMDAS, LWS and DARTS), they are computed as the bottom-level of the task in the task graph, which is the minimum time needed from the start of the task to the completion of the whole graph, assuming unbounded resources [START_REF] Alias | A Compiler Algorithm to Guide Runtime Scheduling[END_REF]. The PaRSEC AP scheduler uses its own set of priorities (although we noticed no difference when using bottom-level priorities).

We measure the obtained performance as the throughput of elementary computational operations performed per time unit (in GFlop/s), as well as the total volume of data transferred either between CPU and GPUs in the case of distributed memory with GPUs, or between CPU and disk in the case of shared memory. When measuring the throughput, the cost of computing the schedule is considered. Each point in the following plots is the average of the performance obtained over 10 iterations. For most of the results, the deviance is less than 2%, thus we do not show error bars in the following graphs. We plot the performance obtained with various Table 1: Amount of data transfers on the last point of Figure 5.

problem sizes, ranging from a few hundreds MB up to 106 GB in order to test all strategies on various memory conditions.

6.1.1 Distributed memory with GPUs. We performed experiments on Tesla V100 GPUs (using cuBLAS 10.2 GPU kernels with single precision), equipped with a 12 GB/s PCI bus. Our application scenarios are the Cholesky decomposition and the LU factorization. We use tiles of size 1920 as it allows to achieve best peak performance on GPUs. Although being separate implementations for flexibility, our applications are identical to those of the Chameleon linear algebra library [START_REF] Agullo | Better -a Hybridization Methodology to Develop Linear Algebra Software for GPUs[END_REF]. In the case of the PaRSEC-AP scheduler, we use the DPLASMA implementation of the Cholesky decomposition.

6.1.2 Shared memory with CPU. We used an AMD EPYC 7642 48 cores/CPU with disks that sustain a 350 MB/s bandwidth. The application scenario is the LU factorization. We use tiles of size 320, which is an optimized size for CPU cores.

Cholesky factorization with GPUs

Single GPU case. Figure 5 shows the results obtained by the various algorithms using one GPU. The dotted horizontal black line represents the maximum throughput that the GPU can achieve when processing the tasks for Cholesky without I/O, and is thus our asymptotic goal. The green dotted vertical line denotes the largest input that fits into the GPU memory.

From Figure 5 we can see that LWS and EAGER greatly suffer from the memory constraint, as their performance plummet after the green line. With only 1 GPU, they both process tasks in their natural order of arrival, resulting with a poor progress on the critical path for EAGER and a large number of data loads for LWS (see Table 1). On this table, "bus limit" is the amount of transfers that can be done during the minimum time for computation (given by the bound on the throughput), thus the hard limitation induced by the PCI bus bandwidth: a strategy exceeding this amount necessarily requires more time for the data transfers than the optimal time for computation. LWS and EAGER are both above it.

DMDAS has more sustained performance but is far from the asymptotic goal on large working set sizes. This is due to a conflict between data prefetching and eviction. Once the GPU is filled with data, it is not clear for DMDAS whether some data should be evicted in order to perform more prefetches. So it will rather stop prefetching data as long as all the data currently in the GPU will be useful for the subsequent tasks to be executed there. DMDAS does not reassign tasks according to the new data loaded on the GPU because it does not have a global view of the set of data and tasks, and thus cannot strike a balance between prefetching and eviction.

To better understand those results we can have a look at Figure 6. It corresponds to the 8th point of Figure 5. It shows the processing order of each task on the first 4 iterations of the Cholesky factorization. Each small square is a task. The first 1000 processed task are in red, the next 1000 in green, then blue, yellow, magenta, cyan and orange. Within each color, the fade (from light to dark) represents the processing order. The black square represents the amount of tiles the GPU can load in its memory. We can see that DMDAS processes tasks following anti diagonals (because of task priorities).

If we look at the 1000 blue tasks for DMDAS, we can see that these diagonals do not allow much data reuse (there are only data shares between the k iterations), and if the memory cannot hold more tasks, the affinity on the rows and columns cannot be found, resulting in multiple loads of the same rows or columns. AP behaves similarly to DMDAS. It uses the expected completion time of tasks and sorts them by priority, resulting in similar results.

DARTS is able to maintain good performance while the working set size increases. DARTS also processes task in a diagonal while it can fit in memory (task in red on Figure 7) but then switches to triangle blocks. We can notice such blocks on the blue and magenta tasks (a triangle on the main diagonal preceded by a square of tasks of the same color on the first few columns). Those triangles and the associated square fit exactly in memory and share a lot of common data and are replicated over multiple iteration (up to k=8) in order to progress on the critical path, while maximizing data reuse. It has been proven that accessing the result matrix by triangle blocks is the most efficient in terms of data transfers [START_REF] Beaumont | O-Optimal Algorithms for Symmetric Linear Algebra Kernels[END_REF], although in DARTS' scheduling, those triangles are only a result of a local greedy strategy to maximize data reuse. On Table 1 DARTS has the lowest amount of data transfers on the largest working set size and is the only strategy under the bus limit, meaning that theoretically, all transfers can be overlapped by a computation, which explains our good performance.

With multiple GPUs. Figure 8 shows the performance with 8 GPUs and Figure 9 shows the amount of data transfers. On Figure 8, the green dotted line now corresponds to the largest matrix that can be stored in the aggregated memory of all GPUs. We first notice that compared to the performance with a single GPU, all strategies are much further from the upper bound. The bus limit value is 250 GB on the last point of Figure 9, and all strategies generate more transfers. With multiple GPUs, some data has to be replicated on various GPU memories, which greatly increases the total amount of data transfers. For matrices smaller than the limit size (green dotted line), LWS achieves the best performance. By stealing work from neighbor GPUs, LWS is able to largely increase transfers using NVLinks, which are much faster than transfers with the CPU memory. With 8 GPUs, the opportunity for such transfers are much more important which explains those performance. This explains why on Figure 9, even with more transfers than DARTS, LWS achieves a better throughput on the left of the green line. For larger matrices, LWS and EAGER have much more data transfers and thus much smaller throughput. They do not consider memory limitation and thus do not favor data reuse. Similarly for AP and DMDAS, the low throughput is associated with high transfer rates on Figure 9, as in the case with one GPU. However, before the constraint, as they consider the performance model to schedule, they are able to distribute tasks in a way that reduces the completion time. DARTS always gives a task to idling GPUs. With a lot of GPUs and few tasks, it is sometimes more efficient to assign many tasks sharing data to a single GPU, even if another one is idling, as it can lead to a smaller completion time overall. DARTS has the best performance once the memory becomes a constraint. Figure 10 represents the task order with 2 GPUs (for clarity) using DARTS on the first iteration of the outer-loop of the Cholesky algorithm. We can still find those triangle blocks that allows us to reduce data transfers, as can be seen on Figure 9. Moreover, there is a good distribution of the data load on the 2 GPUs. When choosing the data to load D opt , DARTS uses a ratio between transfer time and computation time of task using D opt . This favors the selection of a data associated with as many unprocessed tasks as possible. Thus two distinct processing units have a low probability to select the same data as the total work associated with a data is reduced after some of its task is scheduled on another processing unit. This encourages GPUs to work on different datasets, further reducing the total amount of data to load by minimizing the replication of data on multiple GPUs. Moreover, once the workload is big enough, keeping some GPU idle is not beneficial. The sustained performance of DARTS with both 1 and 8 GPUs shows that it is generic enough to adapt to various numbers of processing units.

With multiple GPUs and no memory limitation. Figure 11 shows the results obtained with 8 GPUs without imposing a memory limit (each GPU is equipped with 32 GB of RAM). As mentioned before, DARTS is unable to keep some GPU idle, which leads to slightly worse results than LWS on the first few points. Apart from this, DARTS performs very similarly to LWS, which is the best strategy here. Our scheduling strategy can thus also be used in situations where memory is not a constraint, making DARTS generic enough to adapt to various memory sizes.

LU factorization with GPUs

Results on 4 GPUs. Figure 12 presents performance using the LU factorization with 4 GPUs. This figure does not present results for PaRSEC-AP, as the DPLASMA implementation of LU does not make use of the cuSolver library to solve getrf kernels of the LU factorization. Hence, AP uses a much slower version of this kernel, which makes it impossible for us to compare AP on fair grounds. LWS and EAGER process tasks in their submission order (sorted by priorities for LWS), which makes it impossible to reuse data on consecutive tasks when memory is limited. Hence, these two schedulers end up with 3 times more data transfers than DARTS (see Table 2). DARTS has more sustained performance, and similarly to the Cholesky case, is able to reduce data transfers by distributing the data on multiple GPUs and reusing data for consecutive tasks.

Results on a single GPU and no memory limitation. Figure 13 shows the results for the LU factorization on a single GPU without limiting the memory. The GPU embeds 32GB of RAM, we can see this value on the plot with the green line. DMDAS has more sustained performance than LWS and EAGER. The Ready strategy (see Algo 2), allows DMDAS to re-order task so as to compute first tasks for which the input data is already in memory, thus reducing data transfers. DARTS stays very close to the maximum obtainable GFlop/s for the whole range of matrix sizes. LU factorization has a higher rate of computation-per-byte compared to Cholesky, so that schedulers can more easily stay under the limit induced by the PCI bus. Here DARTS has two times less transfers than this limit (210 GB compared to 447 GB for the bus limit on the last point of Figure 13) and it is able to completely overlap communications with computations, even after the memory limitation, induced by the hardware itself in this case (only 1 GPU).

LU factorization on a multicore CPU

As outlined before, our scheduler is able to consider any memorylimited system, and StarPU manages disk-CPU transfers exactly like CPU-GPU transfers. Figure 14 reports experiments on a 48core CPU with 2 GB of shared memory. In this shared-memory setting, DARTS behaves in a similar way as it does with one GPU: it uses a single plannedTasks queue as well as a single taskBuffer . Again, DARTS is able to achieve good performance even when the memory is limited, while other schedulers see their throughput drop whenever the whole dataset cannot be stored in memory.

CONCLUSION

In this paper, we have focused on the problem of scheduling tasks in runtime systems to handle very large datasets that do not fit into the memory of the processing units. We have largely improved a scheduler for the StarPU runtime system, named DARTS, to cope with task graphs. Our scheduler is mainly focused on data locality but also takes task priorities into account. We have perform experiments with two classical linear algebra operations: Cholesky and LU factorizations. Thanks to its modularity, DARTS reaches very good performance in a large variety of situations, from multicore CPU with shared memory to multiple GPUs with distributed memory. Among available competitors, DARTS in the only scheduler to reach good performance in memory-limited scenarios, and it also ranks among the best ones in all settings. Future works include taking advantage of the modularity of DARTS to design hierarchical schedulers for large distributed platforms, and to combine it with other schedulers (such as work stealing) to benefit from all their features, as (locality-aware) work stealing is efficient to balance load among distributed nodes, while DARTS allows to cope with limited memories.

Figure 2 :

 2 Figure 2: Platform topology of multiple GPUs with distributed memory.

Figure 3 :

 3 Figure 3: Taskset from the Cholesky factorization. Tasks with bright colors are tasks ready to be computed at a given time.

8 :

 8 Add D j to memory(PU k ) Algorithm 2 Ready reordering heuristic, called by PUs Require: List L of assigned tasks 1: while L ∅ do 2:Search first T ∈ L requiring the lowest amount of data transfers 3:

Figure 4 :

 4 Figure 4: Task flow in StarPU when using DARTS

Algorithm 3 2 : 6 : 7 : 9 :Remove D opt from dataNotInMem k 10 :Append T to plannedTasks k 13 : 15 :

 32679101315 DARTS scheduler on PU k When PU k requests a new task 1: if plannedTasks k = ∅ then ▷ We need to fill plannedTasks k for each data D ∈ dataNotInMem k do 3: Compute S 0 (D), S 1 (D), max_prio(D), 4: computation_time(D), task_left(D) and transfer_duration(D) Choose the data D opt with the smallest ratio, tiebreak in this order with |S 0 (D)|, max_prio(D), |S 1 (D)| and task_left(D) if |S 0 (D opt )| > 0 then 8: Append S 0 (D opt ) to plannedTasks k else if |S 1 (D opt )| > 0 then 11: Choose task T with highest priority from S 1 (D opt ) 12: Remove the inputs of T from dataNotInMem k 14: else Choose task T with highest priority from readyTasks 16: Append T to plannedTasks k 17: Remove the inputs of T from dataNotInMem k 18: Return head of plannedTasks k • S 1 (D): the set of tasks that depend only on D, some data already loaded in the memory of PU k , and 1 additional data. • max_prio(D): the highest priority of a task in S 0 (D) if |S 0 (D)| > 0, otherwise the highest priority of a task in S 1 (D). • computation_time(D): the sum of the durations of the tasks in S 0 (D). • task_left(D): the sum of the durations of the tasks in readyTasks that use D as an input. • transfer_duration(D): time required to load D to PU k .

Figure 5 :

 5 Figure 5: Performance on the Cholesky factorization with one Tesla V100 GPU. Memory limited to 2000 MB.

Figure 6 :

 6 Figure 6: Visualization of iterations 1 to 4 of the Cholesky factorization with DMDAS and 1 GPU.

Figure 7 :

 7 Figure 7: Visualization of iterations 1 to 4 of the Cholesky factorization with DARTS and 1 GPU.

Figure 8 :

 8 Figure 8: Performance on the Cholesky factorization with 8 Tesla V100 GPUs. Memory limited to 2000 MB per GPU.

Figure 9 :

 9 Figure 9: Amount of data transfers on the Cholesky factorization with 8 Tesla V100 GPUs. Memory limited to 2000 MB per GPU.

  (a) Task processed by GPU 1.(b) Task processed by GPU 2.

Figure 10 :

 10 Figure 10: Visualization of the first iteration of the Cholesky factorization with DARTS and 2 GPUs.

Figure 11 :

 11 Figure 11: Performance on the Cholesky factorization with 8 Tesla V100 GPU. Hardware limitation of each GPU memory at 32 GB.

Figure 12 :Table 2 :Figure 13 :

 12213 Figure 12: Performance on the LU factorization with 4 Tesla V100 GPU. Memory limited to 2000 MB per GPU.

Figure 14 :

 14 Figure 14: Performance on the LU factorization with AMD EPYC 7642 48 cores/CPU. Memory limited to 2000 MB.

https://files.inria.fr/starpu/testing/master/doc/html/Scheduling.html# DMTaskSchedulingPolicy

The code to reproduce the results of this paper, including DARTS and the applications we used, is available at: https://shorturl.at/ghORU


The Point of View of a Stone: Looking at the Colonization of the Northern Plains from the Standing Rock

Thomas Grillot, Centre d'Études Nord-Américaines (CENA) The Standing Rock Sioux Reservation owes its name to a stone hoisted in 1886 on a tall brick pedestal in front of the local Bureau of Indian Affairs (BIA) agency in the small town of Fort Yates, North Dakota (see fig. 1). Now strongly associated with Sitting Bull and the Hunkpapa band of the Lakota Sioux, and with a large movement to oppose the building of a pipeline north of the reservation in 2016, this BIA local office could have had a different destiny had it remained in its original location, at the mouth of the Grand River in present-day South Dakota, where it was built to deliver rations to another band of Lakotas, the Sihasapa (or Blackfeet band). The Missouri River decided otherwise: in 1873, threatened by its periodic floods, the agency had to be transplanted north, twenty-five miles below the mouth of the Cannonball River, in close proximity to the stone known as "Standing Rock" and to Yanktonai bands, who were Dakotas, not Lakotas. At the time, the Standing Rock was a landmark known to several Native groups. The BIA agent in charge of relocating the agency, Edmund Palmer, thought it a fitting namesake, and he decided to have the stone moved to the new agency. Today the stone sits in front of the Standing Rock Sioux Tribe's administrative complex, the former BIA agency. There, it overlooks the Oahe Lake, one of the main reservoirs on the upper reaches of the Missouri. Almost a century after the relocation of the stone, in 1963, the local American Legion post, the Lion's Club, and the reservation's tribal council dedicated an explanatory panel near the base of the monument's pedestal. It is now an established stopping point for tourists, and the short narrative transcribed on the panel connects the stone, the monument, and a legend. Although the rock was not originally Sioux or even located on Sioux lands, visitors are told, it was regarded by them as sacred. The Sioux interpret it as the body of a young woman, whose refusal to follow her band resulted in her being petrified with her child on her back. Its location by the Missouri River, the anonymous authors of the panel add, gestures toward "the empire once held by the mighty Sioux." Ideological as it is-and the panel bears the mark of a distinctly colonial mindset despite the tribal council's involvement in its elaborationthese few lines represent an apt synthetic explanation of the nature of the stone and of its place in local history. They allude to some of the most tantalizing problems that the stone has posed to those who have come into contact with it: Who was the woman on it whose features visitors were (and are) invited to recognize? Is the stone a woman, a rock, or both? According to whom? Was its monumentalization followed by a desacralization and a deconnection of the stone from reservation life? And there is also the intriguing question of how a being/object such as the Standing Rock can be so central to the identity of a Sioux reservation without being unequivocally regarded as Sioux. For the panel here merely reflects received wisdom: the stone, all witnesses agree, was taken over from the Arikara; the woman herself, many Sioux assert, belonged to that tribe.

These questions invite the consideration of larger issues of ethnic identity formation, place-making, the writing of history, and the role of colonization in shaping these social activities. While we know much about the worship of stones in the northern Plains, we are often at pains to follow the history of one individual stone over centuries. The case of the Standing Rock is an opportunity to understand what we miss in the process. In particular, the stone and its legends stand as a reminder of the very diverse ways in which Native people adapted their legends, memories, and history to the tumultuous time of forced assimilation. First, because the stone cir-culated among tribes, it forces us to examine what we know of the social and territorial boundaries between bands with various tribal connections in the reservation era. In line with recent studies that emphasize exchanges and elastic boundaries between groups operating on the northern Plains (Posthumus 2016: 366-77; Rzeczkowski 2013: 5-11), it encourages us to consider the perpetuation of this diversity well into the twentieth century. Second, it is an opportunity to follow in detail the reshaping of a specific tradition and make sense of its trajectory in an analysis that goes beyond resistance or dissimulation. To approach the various ways in which both Natives and Euro-Americans repurposed the stone for reservation life, I use sixty written renditions of the legend, some of them directly related to oral tradition, and connect them with maps, travelers' diaries, priests' reports, administrative correspondences, and individuals' papers.

What emerges out of the record is paradoxical: Even as the monumentalization of the stone by Euro-Americans marked the beginnings of the reservation era and the subjection of Natives, the circulation in written form of its legend created new conduits for the creation of Native narratives, values, and traditions, and their dissemination across a whites/Natives divide. Moreover, published circulation of the legend helped make it relevant to the contemporary challenges of colonization, Christianity, and tourism. Rather than an end point, colonization and monumentalization turned out to be new chapters in a century-old story. Finally, the stone and its legend's relevance to contemporary Native life was never limited to identity politics: even as the stone became an identity marker for Standing Rock denizens, the interpretations attached to it developed along gendered or generational divides that crossed reservation boundaries. While immobilized and monumentalized, the stone, in other words, remained a mobile actor of social life in North Dakotan Indian country, not a neutralized piece of decontextualized heritage. It remains today, not as a witness to past beliefs, but as a trace of the continued production of social relations through the making of place in colonized North America.

Questions of Ownership

The Standing Rock presents a riddle to ethnohistory. There is no shortage of historical records to let us imagine the history of the stone before the BIA showed an interest in it in 1873. This very abundance, however, leaves us with nothing more than hypotheses as to its origins.

To be sure, its complex identity as both Arikara and Sioux points us to the world in which it was disputed: the ecological and geopolitical universe of the upper Missouri region between the mouths of the White and the Knife Rivers that saw various indigenous groups struggle for the control of natural resources and trade goods in the eighteenth and nineteenth centuries. The stone's uncertain ownership mirrors the ambivalent relationship of these groups, indeed the opportunistic, alternatively symbiotic and parasitic nature of their interactions. While the Sioux, Lakota or Dakota, were undeniably newcomers in the region in the 1700s, by the end of the century they had gained a firm foothold along the Missouri River, controlling vast areas west and east of it, but they also managed to forge peaceful, coexisting relationships with peoples long established in the region. As late as the Leavenworth expedition of 1823, some Lakota bands could volunteer to attack Arikaras alongside US troops, and then quietly retire after discreet negotiation (Posthumus 2016: 361). Although the later part of the century saw more aggressive, indeed more clearly expansionist behavior on the part of Sioux bands, such intermittent neighborliness never disappeared. Throughout the period, horticulturalists, decimated by disease more than by nomadic enemies, were forced to regroup in fewer, better fortified vil-lages north of their original locations. Yet warfare, even of the most brutal kind, did not preclude the establishment of kinship ties, the borrowing of ceremonies, or military alliances between groups. It was only in the second half of the nineteenth century that a clear-cut opposition between sedentary (Arikara, Mandan, Hidatsa) and nomadic (Lakota and Dakota) peoples came to define interethnic relations in the upper Missouri world-just when Euro-Americans emerged as the dominant player in the regional game (Krause 2016: 323-27).

As early as 1805, non-Native newcomers noted the existence of stone formations in the regions that Natives understood to be petrified humans and dogs. That year, Arikaras showed Lewis and Clark several exemplars near present-day Hermaphrodite Creek, South Dakota (Biddle 1962: 66). A year later, French trader Joseph Graveline designed a map based on information given by Arikara chief Ankedoucharo (Piaahiitu'), who loca-ted a woman and her dog, both petrified, near the mouth of the "Ouitahou" or Grand River (Graveline 1814; Posthumus 2016: 374). These early references signal a starting point for the history of the Standing Rock. The mention of a petrified dog in Arikara territory, in particular, is congruent with later accounts of Standing Rock: in 1886 BIA agent McLaughlin monumentalized the Standing Rock stone to protect it after a petrified dog associated with it was turned into building material by settlers at Fort Yates (McLaughlin 1910: 36). If the petrified dog that was destroyed was the same as that identified by Ankedoucharo, this would help explain how an Arikara landmark located near the mouth of the Grand River became identified with the Lakotas/Dakotas in the Fort Yates area.

Three accounts published between 1909 and 1916 insist that Sioux owned the stone and that it was moved by travois on both sides of the Missouri River (Place 1910: 2; McLaughlin 1910: 35-39; McLaughlin 1916: 40-41). Only one account, that of James McLaughlin, gives the name of a specific group (the Lakotas or "Tetons") as that of the legitimate possessors of the stone, while also identifying the Lower Yanktonai as its guardians. Contrary to McLaughlin's attempt to give the stone an official Sioux "owner," however, practically all informants consulted in the twentieth century regarded the stone as Arikara. Indeed, the northward transfer of the stone could quite possibly have been accomplished by the Arikara themselves. Yet witnesses from that group interrogated in the 1920s pointed to the Fort Yates area, not to the Grand River, as the original location of the Standing Rock. One gave the neighborhood of Fort Yates as the site of the petrification itself; other Arikaras recognized the Standing Rock as a grandfather or medicine stone that had been located at the center of their village prior to their migration to Fort Berthold. 1 The "Medicine stones" were indeed a well-known feature of Arikara (and Mandan) villages and religious life-and a clearly male, not female godly figure. First mentioned by French explorer Jean-Baptiste Trudeau in 1794, accounts of medicine stones reappeared in accounts by other Euro-peans in the area such as Maximilian zu Wied-Neuwied, Lewis Morgan, and others throughout the nineteenth century (Trudeau 2006: 115-16; for Maximilian, see Thwaites 1906: 339-40; Morgan 1959: 161-62). Some medicine stones were abandoned; others were moved; and new medicine stone shrines were erected at each point of the forced migration that led the Arikara, decimated by smallpox and harassed by the Sioux, from the Cheyenne River to the Fort Berthold area. In 1873 and 1908, anthropologists witnessed some of these stones' inauguration ceremonies (Wood, Hunt, and Williams 2011: 171-73). This ethnohistorical record makes our identification of the Standing Rock problematic: if it was indeed a medicine stone that followed the Arikara in their migrations, could it really be the same as the "petrified woman and dog" inscribed on the Graveline map?

For the early history of the stone, Native sources such as winter counts offer some clues. In 1969, James H. Howard noted an interesting entry for the year 1740 in the Yanktonai "John K. Bear" winter count: "woman pouted and turned to stone." This is evidence that the phenomenon for which the Standing Rock came to stand (a woman, out of her own volition, or as a punishment, becomes a stone) was talked about among the Yanktonai since at least the mid-eighteenth century. Writing at a time when anthropologists and psychiatrists had set out to research the cultural component of diseases, Howard chose to go further. To him, the entry signaled a typically Sioux psychiatric ailment: wacinko, or pouting, a self-exclusion from social life due to a feeling of having been slighted, which, in extreme cases, could lead to death. Howard went even further in suggesting that 1740 should be regarded as the earliest mention of the Standing Rock legend itself (Howard 1976: 31-33). He also offered a theory to account for the intriguing intergroup status of the stone: "When the Dakotas took over this territory from the Arikaras, they also took over their reverence for the stones, or at any rate one of them" (Howard 1976: 32). Howard's hypothesis offers a new, Native-centered starting point for the story of the rock while also accounting for its Arikara origin and suggesting its relevance to contemporary Sioux behavior.

The risk of overinterpreting the winter count entry, however, is great. We do not know what the entry meant in the eyes of its maker and the group he stood for. The historicity of the event that the count maker recorded is cloudy. He may have personally witnessed the event or merely heard the story, which may have been known by all or merely a few of his group. Similarly, we cannot know whether he recorded it as he would a strange, outlandish event, perhaps something coming from another group, or as one of the admittedly rare, but nonetheless plausible happenstances that the Yanktonai were ready to regard as historical phenomena. The entry gives the woman no group identity or name, and it leaves the location of the event indefinite. Is it indeed the first mention of the Standing Rock or an example of another stone connected to a woman? 2 Howard's intuition that stones were variously integrated in Native communal life remains the strongest part of his argument.

In addition, one must consider that the Dakota phrase associated with "Standing Rock," inyan bosdata, first appeared in the record in regions distant from the Upper Missouri. In 1824, explorer William H. Keating gave the term as the name of a Mdewakanton band living on the Missouri and the Cannon Rivers in present-day Minnesota, near another remarkable stone feature (Keating 1824: 383). In 1839, Joseph Nicollet recorded an oral tradition dating back to the early 1700s and noted the existence of another inyan bosdata farther west in the Sheyenne River valley (Nicollet 1843: 21, and map). Because no story is attached to these landmarks, their relationship to the Standing Rock monument is difficult to ascertain, at best. They point to the connection of Sioux groups with individual stones, but leave open the question of how these groups interpreted these con-nections. Furthermore, the fact that some bands had developed strong relationships with individual rocks does not mean that all rocks fostered such relationships, or that all were regarded as territorial markers.

The various places occupied by stones and rocks in Sioux practices and ideologies is well documented in late nineteenth-and twentieth-century ethnographies (Dorsey 1894: 447). Sioux respectfully referred to stones as tunkasila or "grandfather" and believed humans could talk to individual stones of all sizes and even ask them for help in recovering objects and persons, curing ailments, or obtaining information. Certain Lakota/Dakota individuals expressed the intuition that "all the rocks and stones were people turned to stone'" (Densmore 1918: 217). In Lakota/Dakota tales, Stone Boy was a prominent character, and at least some innovators were willing to imagine a being named Stone as a primordial force in the universe comparable to the Christian God (Walker 2006: 140-53, 206-15). Non-Indian visitors relying on biblical phraseology were keen to denounce as "idol worship" the practices associated with these beliefs (e.g., Thwaites 1906: 375). They took special note of the daubing of certain stones with vermillion and the depositing of offerings on or next to them-a technique, it should be noted, that was not specific to Sioux and was clearly associated with the Standing Rock as it emerged in the records in the 1870s. These practices also developed along gendered lines. Among Yanktons, for exam-ple, such red-painted rocks stood witness to married women's faithfulness (Olden 1918: 2-3). [START_REF] See | Yankton Data, by Nigesan [Antelope[END_REF] Additionally, it is likely that a few of the most remark-able rock formations honored by specific Sioux groups served as landmarks for the groups to orient themselves in their migrations or even to delimit their respective territories. In the 1940s, Lakota anthropologist Ella C. Deloria interviewed an anonymous Yankton Sioux who recognized the Standing Rock monument as a landmark once located between Fort Yates and the Cannonball River, signaling the northernmost limit of his group's migrations. [START_REF] Deloria | Interviews with Yanktons on Land, Place Names, etc. Inter-views with William O'Connor[END_REF] Whether or not the stone had been moved around before this placement between the Yates and the Cannonball Rivers, Standing Rock was clearly in that position as a fixed landmark, so much so that it was identified as significant by the BIA. In 1873, fearing that floods would wash away his compound at the mouth of the Grand River, Agent Edmund Palmer, a Civil War veteran then in charge of the "friendly" Sihasapa, thus made sure to relocate his agency within a reasonable distance of the stone, near present-day Fort Yates and to appropriate the English name of the monument for his new residence.

The idea that Dakotas and Lakotas were introduced to the "worship" of stones by Arikaras is unlikely. But the idea that they accepted the special sacrality of some stones because they had witnessed Arikaras' special rev-erence for them is not. While Arikara witnesses are the most insistent that the stone was theirs and that they lost it to the Sioux, Sioux testimonies suggest that the Standing Rock was originally "foreign," a status that was understood even after the stone had been appropriated and honored in Dakota/Lakota fashion (Place 1910: 2).

Indian observers uniformly designated the woman behind the Standing Rock as Indian but not a Sioux, with most regarding her as an Arikara. For Sioux, especially for the Yanktonai bands that lived in close proximity with Arikaras, Mandans, and Hidatsas, the stone was visibly associated with the practice of intermarrying with neighboring tribes, whose status was ambivalently that of enemies and of partners. The legend expressed this ambivalence in transparent terms: the Arikara woman was petrified after having refused to follow her Sioux husband, who had taken a second, Sioux wife. In this form at least, the legend cautioned Dakota/Lakota men against the risks of an Arikara marriage and warned women, maybe especially women with an Arikara background, on the consequences of disobedience. The gendered and ethnicized nature of the stone, as expressed in the nar-ratives, found echoes in real-life behavior. In the 1870s, Sioux boys were observed stealing offerings that old women left by the side of the stone; conversely, old Sioux women were overheard asking the stone for pros-perity and a long life for them and their children. [START_REF]The Legend of Standing Rock[END_REF] In the 1920s, a prominent Sihasapa woman expressed her lack of interest in the stone, which she identified as a wiciyelo (or Yanktonai) object, and claimed not to know the legend itself. [START_REF] Welch | The Standing Rock[END_REF] Far from an object of universal and unambiguous reverence, the stone never lost its association with otherness, and fostered polar oppositions between young and old, Sioux and non-Sioux, women and men, and Yanktonai and Lakota groups. Its strong association with the Arikara and its likely status as a spoil of war of sorts never entirely disappeared. Simi-larly, on the Standing Rock Reservation, Sioux inhabitants knew of and avoided former Arikara places of habitation for fear of ghosts, and they remembered their presence in Sioux toponyms (the Grand River, for example, was Padani Tawakpa, or Arikara River; Howard 1976: 56). If indeed Sioux (possibly Yanktonai) "learnt" the stone's sacred status and a version of the legend from Arikaras (possibly Arikara women), the appropriation that ensued repurposed both the stone and the legend to serve objectives internal to Sioux bands-especially tensions between the sexes. The monumentalization of the rock in 1886 did little at first but add another layer of meaning to these prior appropriations and renew Native competitions over the stone.

Legends and Reservation Life

To be sure, the act of placing the rock on a pedestal by the BIA was not a mere formality, and the gesture has been the object of contradictory inter-pretations. There is no doubt that the Standing Rock monument was part of a power relationship between BIA agents and Lakota/Dakota medicine men and that the stone was drawn into the struggle for spiritual legitimacy that mobilized colonizers and colonized in the Northern Plains in the late nineteenth century. Contemporary Euro-American accounts at the time emphasized Native consent to its monumentalization, without necessarily hiding the fact that monumentalization was aimed at immobilizing the Sioux and their stones. Euro-Americans openly denounced the "tricks" they imagined medicine men performed with stones and rejoiced in the conviction that an immobilized rock would lay bare the medicine men's pretense of mastering the supernatural. Native spiritual men were well aware of this hostility. [START_REF]For the non-Indian side of this issue, see "Curious Indian Ceremony at Standing Rock Agency, the Sioux Chief, Fire Cloud, Dedicating the Sacred Standing Rock to Peace and Plenty," Frank Leslie's Illustrated Newspaper[END_REF] And after 1886, Euro-Americans essentially wrote the legend to support their viewpoint. They took pains to give the story of the stone a backdrop of intertribal conflict and emphasized the pacification they boasted to have brought to the region. Contrary to their accounts, we need to stress that rather than serving as an end point, colonization and monumentalization were merely a new chapter in the story. The story of the stone continued to structure relations between generations, genders, and members of different tribal groups, but in an environment altered by the irruption of settlers and a state agency intent on establishing control over Indian practices involving the sacred.

The role of James McLaughlin, and his wife Marie-Louise, in this restructuring cannot be overemphasized. In 1886, James, a Canadian immigrant who was the ninth BIA employee to head the agency since 186 9, apparently obtained the consent of various Lakota (not Dakota) headmen to put the stone on a pedestal. Forty years later in 1916, Marie-Louise, who portrayed herself as a woman "of one-fourth Sioux blood," was the first to publish the legend in book format in aversion that can reliably be regarded as based on Native tellings (McLaughlin 1916: 40-41). The couple's accounts of the stone diverged in significant ways, but they agreed that it stood as a witness to Sioux' connection with the sacred-a point that would from then on be central to the social role of the stone. James himself recognized the Standing Rock as a "sacred relic," while Marie-Louise used the term wakan, which she translated as "holy" in her book, Myths and Legends of the Sioux. Both concluded their narratives by signaling that the stone had become a monument and the namesake for an agency and a reservation (McLaughlin 1916: 41; McLaughlin 1910: 36).

Its sacredness was also a thing of the past. James presented the mon-umentalization as a rescue operation, in line with the BIA's ambition to protect Natives against unscrupulous whites. Euro-American influx in Lakota/Dakota territory was indeed closely followed by the widespread appropriations of stones by settlers. Throughout North and South Dakota, they were either destroyed or spirited away and turned into construction material in the first decades of the twentieth century. On the Standing Rock Reservation, especially in the Cannonball district, which had already seen other sacred landmarks change hands between Arikaras and Sioux, several rock features disappeared within the first years of the reservation era. In affirming the Lakotaness or Dakotaness of the stone, the McLaughlins paved the way for the new place that the stone assumed in local public life in the twentieth century as a central identity marker for the reservation. For the monument's inauguration, James enlisted Fire Heart, a Sihasapa med-icine man, and Sitting Bull himself. This was a master stroke: it vindicated his claim that the BIA's intervention in Sioux religious life was agreeable to all, reinforced his agency's identity and his personal status as protector, and mitigated the potentially hostile nature of the takeover. [START_REF]Lo, in Dakota, Looks for Citizenship[END_REF] Yet, in his Englishlanguage speech, James identified the stone as part of a lifestyle bound to disappear, as did Marie-Louise when she recorded the legend in Myths and Legends. In the same decades, this re-repurposing of the stone from a landmark to a marker of disappearing Dakota and Lakota spirituality was closely mirrored in a parallel movement: the Arikara's reassertion of their ownership of the stone and of their own understanding of its origins.

Having relocated with Mandans and Hidatsas in the Fort Berthold area in the 1870s, the Arikara maintained their relationship with the stone through storytelling. Their legends were replete with petrification stories (Beckwith 1937: 307n144; Bowers 1963: 396n24). Although the specific tale of Standing Rock continued to be told and shared with anthropologists (Dorsey 1904: 120; Gilmore 1921: 15-17), the stories were vastly different from Marie-Louise McLaughlin's version. In recorded Arikara tales, the petrified woman was an Arikara, but unmarried and, an even more important difference, unwilling to marry. Indeed, it was because the mar-ried state proved unbearable or unattainable for her that she turned to stone, either as a result of shame for her abnormal genitalia (her vulva literally turned into a flower) or precisely to escape her husband and be one with nonhumans. There is no mention of a co-wife here: whether voluntary or not, it was celibacy and sexuality that were at stake, not jealousy and obedience toward one's spouse. The divergence with a "Sioux" narrative seemed unmistakable, and this divergence was further supported by the public affirmation of the Arikara's ownership of the stone, albeit in a par-adoxical way: in 1921, a new stone was erected in Fort Berthold as a replacement for the one lost to the Sioux in elaborate ceremonies celebrating "medicine stones." [START_REF] Gilmore | Making Records of Ancient Rituals of the Arikara Tribe in North Dakota[END_REF] This was part of a larger movement to map out former Arikara territory and traditions in collaboration with anthropologists and archaeologists (Thiessen, Wood, and Jones 1979: 145-67; Will 1924).

The competitive affirmations of distinct versions of the Standing Rock legend can be interpreted in at least two ways. It is possible to insist that reservations alienated peoples who had been at times closely associated and encouraged them to develop independently from one another. In this view, colonization was a watershed, a point in time and a process that tilted the balance from partnership to separation. Another approach, which we favor here, acknowledges that competition between traditions such as that evi-dent in the case of the Standing Rock did not foreclose collaboration and that collaboration as well as competition continued after relegation to reservations. Colonization severely limited old channels of exchanges between Sioux and Arikaras, such as regular visits between camps, but also opened new ones. Religious conventions and visits exchanged between Native peoples associated with church denominations were especially important sites for exchanges. They provided the terrain for continued intertribal dialogue over the Standing Rock, and were crucial to the creation of the only version in Lakota now at our disposal: Ella C. Deloria's 1932 transcription in Dakota Texts (Deloria 1932: 221-23).

The Deloria version is strikingly similar to the ones collected among the Arikaras in the first decades of the twentieth century. It foregrounds a young woman's attempt to resist her relations' desire for her to marry, her escape from camp, and her final inability to escape petrification. Throughout the narrative, Ella Deloria's Lakota informants are careful to underline the moral and social principles that guide the woman's and her family's behaviors, and they are especially anxious to stress the importance of respect among kin. This principle is central to Ella Deloria's own inter-vention as a Native anthropologist, whose work is so fundamental our understanding of Dakota/Lakota culture. She worked for her own people, as the loyal daughter of Philip J. Deloria, an Episcopalian mixeddescent minister connected to Yankton and Sihasapa bands and active as a mis-sionary on the Standing Rock Reservation. It is from this very specific position that Ella Deloria undertook to collect "Sioux tales" for Franz Boas. It gave her access to the network of Christianized elders known to her father (two of her three informants for Dakota Texts were clergymen themselves) and severely restricted her access to those who had rejected conversion. 10 It also shaped her conviction that Indian families were under assault from modern society and that this assault took the form of adultery, divorce, and disrespect among relatives and generations, an approach especially evident in her unpublished manuscript "The Dakota Way of Life." From this analysis emerged her determination to preserve the correct rules of behavior according to Lakota tradition, which she assumed would, if adhered to, help Indian families overcome the crisis.

Published in 1932, Deloria's legend of Standing Rock insisted on the new role that American Indian ministers had envisioned for Native tradition since the end of the nineteenth century: as a faithful companion, a complement, and, occasionally, an improvement of Christianity. With its emphasis on shame and respect, the Standing Rock tale, in particular, demonstrated Lakota tradition's potential to reinforce a respectable version of Native identity, one that was at once compatible with Christian values and a valid competition to them. Deloria herself worked hard to document the coherent organization of Lakota culture toward one goal: harmony, which shaped her efforts to reconstitute the lost world of Lakota life in the Northern Plains. Late in life, she collaborated closely with James H. Howard to produce a geography of Sioux occupation of the region in which stones figured prominently. Her work in this area was crucial to Howard's own understanding of the role of stones in Sioux life. [START_REF] James | Interviews with Yanktons on Land, Place Names, etc[END_REF] Early on, Deloria's familiarity with English and her broad education put her in the position to act as an intermediary between Euro-Americans and Indians to foster this goal. It was in this capacity that she translated Paul Yellow Bear's words into English in 1916 (Olden 1918: xix). Yellow Bear, an Arikara Episcopalian minister, was at the time visiting Philip Deloria's St. Elizabeth Mission in South Dakota. He was conversant in Lakota and took this opportunity to share his version of the Standing Rock legend with his hosts. It is strongly reminiscent of the one collected by Ella Deloria a few years later, and strikingly dissimilar to that of Ella Waters, his own daughter, which was recorded in the 1970s (Olden 1918: 60-61; Parks 1991: 313-14). Yellow Bear's version is definitely a man's view, with his emphasis on the maiden's "cold heart," but, like Deloria's, his version exhibits a pedagogic insistence on correct behavior within families, sometimes in such seemingly secondary details as the correct sitting position or the excision of any unseemly allusion to female genitalia. What was only an aside in McLaughlin's version-the relationship between the petrified woman and her family or her in-laws-was a central element in Yellow Bear's rendering, indeed the principal motivation for the telling of the tale, in which polygyny disappeared entirely. His was a complex act of cultural translation, indeed diplomacy: he was giving, in Lakota, for the benefit of an audience that associated Sioux and Euro-Americans, a desexualized, yet distinctly Arikara version of a tale that was associated with the reservation's namesake stone. In this act of "sanitization" of Native tradition, Yellow Bear went further than whites: in 1903, when ethnographer George A. Dorsey was confronted with the then scandalous aspects of the Arikara tale, he had not erased them but opted to make them less accessible by turning to Latin (Dorsey 1904: 120).

In such settings as reservation-based missions, semi-ritualized intertribal encounters thus directed Natives of various tribal affiliations to adopt similar strategies, producing stories that, once decontextualized, could appear essentially Arikara or Lakota but actually had their origins in renewed close association of members of each group, and ultimately, in the same social and political needs. The specific case of the Standing Rock demonstrates how, without obliterating other versions, Native actors operated a selection of legends and, within legends, of elements that were compatible with a new moral climate. The result was greater, not smaller, diversity in the interpretations of Native traditions, a diversity that had little to do with individual idiosyncrasies and depended heavily on phenomena affecting reservation communities throughout the United States, especially the pressing need to demonstrate the relevance of Native moral norms and the legitimacy of preserving Native traditions. [START_REF] On | Paul Yellow-bear and His People[END_REF] Performance, Writing, and Canon: New Oppositions Colonization thus opened a new field for intertribal contacts, one that mandated the careful selection of traditions, but did not prohibit diversity or creativity. And non-Indians played a part in these processes. In the first decades of the twentieth century, Native storytellers had to contend with Euro-American versions of their tales that were at best ambivalent regarding the value of Native tradition. As early as 1893, Native storytellers had understood the need to use English and the printed work to counter these worrisome appropriations. [START_REF] Henry | Talks and Thoughts of the Hampton Indian Students[END_REF] By 1916, when Yellow Bear spoke at St. Elizabeth's mission, the threat to Native traditions was clear to all present, as was the necessity to teach, not simply tell proper versions of the tale. On the Standing Rock Reservation, non-Indian visitors and settlers had not sat idly by while the BIA consecrated the rock as a symbol of Native beliefs and had its legend published for the first time. Between 1873 and the 1920s, print served as a handmaiden to colonization, disseminating versions of the tale that poked fun at Natives' supposed credulity, ironically emphasized the challenges of polygyny, and told of intertribal and consistently starcrossed romances for the benefit of a readership of Euro-Americans. Pub-lished in newspapers, these "legends of Standing Rock" spoke to a romantic tradition that harked back to Longfellow and had been routinized in tour guides as early as the 1860s. [START_REF]An Indian Legend[END_REF] Mentions of rock formations, Indian maidens' suicides, and ill-fated love stories promised visitors throughout the old Northwest, the Plains, and the Rockies, that the Wild West had not entirely vanished with the rollback of Indian groups and the advent of the railroad. The Standing Rock stood at the end point of this consumption of landscape and reimagined Native traditions. Unspectacular, indeed rather disappointing to many tourists on account of its small size, the rock needed to be re-enchanted to work as an identity marker and tourist attraction. Here also competition gave way to collaboration, or at least convergence among Native peoples and between Natives and Euro-Americans.

The nascent Euro-American community of Fort Yates was especially interested in some kind of dignification of Native tradition because, in the 1910s, the settlement seemed about to be connected by railroad to the wider world, which would draw a flow of visitors interested in Indian folklore. Local authors were aware of the need not to go too far in denouncing Native deficiencies, and-in books, newspaper articles, talks, and informal conversationsthey defended Native tradition while also providing rationalizing explanations of the story "behind" the rock. The idea that the petrified woman could have committed suicide appeared in 1912. [START_REF] Welch | Lecture to Accompany pictures of Sioux Nation Powwow[END_REF] It would eventually give rise to Howard's wacinko thesis, and wacinko became known to local non-Indians at precisely this time. [START_REF] Beede | Central Classified Files 1907-1939[END_REF] But in the same breath, Euro-American tellers of the tale stressed the fact that the stone was imbued with power and, therefore, dangerous. [START_REF]Standing Rock[END_REF] Credibility was a vital part of the legitimation of the story and of its inclusion in larger anthologies of "Indian" traditions (Lyback 1925: 225-26; Skinner 1896: 125; Gridley 1939: 94-95). And Euro-American tellers' success in attracting visitors can still be measured today by the initialed graffiti visible on the second, higher pedestal given the rock in the 1890s.

In parallel to these "for-tourists" versions, non-Indians used the Standing Rock story with another target group in mind: Native children. In 1901, the Indian Office recommended that reservation teachers approach Native legends as a first step into the study of history. [START_REF][END_REF] Marie-Louise McLaughlin's book, written to offer "the very texture of the thought of a simple, grave, and sincere people, living in intimate contact and friendship with the big out-of-doors that we call Nature," seems to have been prime material for instruction on Standing Rock (McLaughlin 1916: 10). By 1933, McLaughlin's rendering of the tale had become standard fare in BIA classes, when Louisa Long Soldier, an eighth-grader in Fort Yates, won a county-wide declamation contest reciting the legend. 19 Long Soldier's text quoted abundantly from McLaughlin's book, gave names to heroes whom Marie-Louise had left anonymous, provided additional ethnographic details, and turned the piece into a spectacular sample of Indian life. The young pupil's rendition exemplified the crucial phenomenon that solidified the dominant position of Marie-Louise's version in public life while allowing for all manner of adjustments to fit the necessities of the situation or the narrative standards of the storyteller: the interaction between orality and writing in performances given for the benefit of interracial audiences.

In the 1950s the BIA commissioned an Oglala Lakota artist, Andrew Standing Soldier, to paint a mural including the legend in a Fort Yates school. It also encouraged reservations schools to reenact the legend through annual performances, a way to connect pupils to the outside world. Murals, parades, and especially theater representations were indeed crucial moments when Euro-American educators sought to legitimize their work vis-à-vis their surroundings and demonstrate their success at fitting Indians for modern life. When Long Soldier recited the legend, she was not the first to have sought to dramatize it-the legend had already been performed on the Pine Ridge Reservation. [START_REF]Poem of Standing Rock Legend Read by Lindberg Today[END_REF] Had Ella Deloria written for a nonacademic readership in the 1930s, she might very well have adapted the legend for the stage herself, as she did at the Haskell boarding schools in Kansas in the 1920s and would do again in Eastern Cherokee country in the 1940s. [START_REF]On Deloria's fondness for dramatic performance, see her correspondence[END_REF] Dramatization of the legend of Standing Rock in the form given to it by Marie-Louise McLaughlin would, at any rate, continue well into the 1970s. [START_REF]Standing Rock Heritage II[END_REF] Paradoxically, it was thus the colonial school system, with its emphasis on articulating English, writing, and public performance that enshrined the version of the legend that most clearly emphasized intertribal marriages and the past as well as the complex relations between the Arikara and the Dakota/Lakota.

It is at this juncture that we can reexamine the connection of the stone and the legend, along with the complex identity nexus they formed after the first hundred years of reservation life. Having been remade into a monument between 1873 and 1886, the Standing Rock ceased to be only the focus of worship and intrafamilial storytelling to become a matter of public interest. But it never became a museum piece. Accessible and made visible by written pieces, it remained a living component of social life on the Standing Rock Reservation. In the 1920s, BIA agents assumed the role of tour guides, told the legend to visitors, took them to see the stone, and were photographed with them in front of the monument. [START_REF] James | Standing Rock Reservation Rich in Traditions[END_REF] The reservation was included in suggested itineraries advertised in national newspapers, and the outline of the Standing Rock was turned into a road marker (White 1936). When, in 1938, the North Dakota Works Progress Administration (WPA) issued its guidebook for the state, the editors based their legend of Standing Rock on the description provided by agents, adding details borrowed from Marie-Louise McLaughlin (Federal Writers' Project 1938: 304, 316). Agency newsletters and reports on the reservation appeared, prefaced by or concluding with either McLaughlin's version or the WPA's. [START_REF] Papers | Standing Rock [Sioux: Reservation Development[END_REF] After World War II, tribal officials inherited and slowly systematized the methods of attracting tourists and investors. 25 Standing Rock's tribal officials, in a bid to attract industry to the reservation, organized a contest to provide the reservation with a distinctive logo, and they selected a design centered on the Standing Rock monument. [START_REF] Schmidt | Central Classified Files 1958-1975, RG 75[END_REF] In 1963, they teamed up with local businessmen to purchase and engrave the explanatory panel that still sits in front of the stone. In 1973, as part of the ceremonies celebrating the centenary of the reservation, tribal officials once again disseminated McLaughlin's English-language, probably Yanktonai version. [START_REF]Standing Rock Monument[END_REF] While these multifaceted governmental interventions in the telling of the legend reinforced the hierarchy among versions, and perhaps created a new divide between tradition in writing and tradition in memory, they did so without ever precluding diversity or promoting rigidly ethnic versions of the tale. Change was undeniable: by the mid-twentieth century, writing had clearly become an essential source of variation, and public performance used publications, not autonomous, oral sources for their inspiration. Tribal programs of cultural revitalization that were instituted in the 1970s relied heavily on written material to continue the work of legitimation of Native cultures started by previous generations, and could or would not reverse that trend (Walker 2006: ix; Jahner 1975: 118). 28 Many texts, authored by Indians and non-Indians alike, disappeared in the process: texts defending polygyny, versions identifying the stone with a man, and renditions authored by Sioux experts such as Robert High Eagle, who collaborated with anthropologists like Frances Densmore but was never able to publish more than article-length descriptions of Lakota tradition. [START_REF] High | The Legend of the Standing Rock[END_REF] The stone's inclusion in networks intent on adapting Native traditions to modern life considerably modified its position on the reservation, connecting the monument to paper, indeed creating a special relationship between the stone and a few canonized transcriptions of its legend. The process was rife with power struggles between Indians and non-Indians. It was also one through which the stone and its legend survived: interethnic and interracial competition and collaboration consistently alternated throughout the twentieth century to repurpose the stone for reservation life and help it serve local desires to gain status and respectability vis-à-vis outsiders. Indeed, old meanings survived and also received the consecration of publication. The cautionary nature of the tale, for example, figured prominently in late published versions (Matson 1972: 55-58; Power 2002: 147-59) and testified to the maintenance of intrafamilial approaches to the rock that had been evident in the record since the early decades of the century (Zitkala-Sa 1921: 96-97). Old practices associated with the stone, such as the detection of faces and signs on the rock remained as well. [START_REF]Religion among the Dakotas," 24; interview with a Standing Rock wanagi wapiya, or spirit healer[END_REF] And the Arikara origins of the legend were never erased to produce an official narrative that would "naturalize" the petrified woman and make her an unambiguously Dakota or Lakota citizen of the reservation that was named after her.

Recovering the various conditions of the production of the "Standing Rock legend" over a century is therefore not merely a way to identify legitimate Native versions, or trace resistance, dissimulation, or survival. It brings to light more complex, indeed paradoxical processes, foremost among which is the cultural productivity of the colonial encounter. Via the cultural idiom imposed by colonization (English-language written matter), the stone, immobilized at some point in the nineteenth century and mon-umentalized in 1886, became an important medium of interaction across racial and ethnic boundaries, a medium that was at the same time physical and immaterial, a monument and a paper creature whose continued exis-tence was legitimized, not prohibited, by colonial agents and even settlers. From a time when the only Euro-Americans living on the reservation were BIA employees, to the 1910s and the massive arrival of white farmers in the region, into the New Deal era, telling the legend became a routine fact of social life, a way to mark a distance with the pre-reservation era while also gesturing toward the contemporary practices of Lakotas and Dakotas on Standing Rock-and to their connection to their supposedly hereditary enemies, the Arikara. In regard to the stone and its legends, colonization imposed the necessity, for Indians as well as non-Indians, to legitimize at least some Native traditions. It involved producing accounts that could travel easily, be adapted for other scenes, both geographical and social, and display Native values respectable to Euro-American sensibilities. Interethnic and interracial collaborations proved decisive in these processes. Prominent converts to Christianity and their families were in a much better position than others to promote their own versions of traditions, and they did so as an inter-reservation group that kept open channels of exchange between tribal groups; Yanktonai versions received a wider publicity than Lakota or Arikara ones; tellers with a greater proximity to the BIA, missionaries, or anthropologists stood a greater chance of seeing their rendi-tion embraced as legitimate. Ultimately, this was perhaps colonization's most durable legacy: it introduced a new hierarchy between versions that is utterly absent from the ethnohistorical record for the prereservation era. That the hierarchy among versions would reflect reallife social hierarchies is perhaps not altogether unexpected. Seeing this connection operate over a century is, however, a clear benefit of a micro-historical approach to colonization in the United States. Looking at very specific practices is especially important if we want to be able to fill some of the gaps in the record. In the case of the Standing Rock, where the tradition was not connected to a particular group or family but disseminated among many and where it circulated intensely, micro-history was in fact the only way to grasp the quiet work that went into preparing Native traditions for life in the radically new context that colonization and settling on the reservation brought about. The stone proved a good vantage point because the Standing Rock stood so clearly at the junction of the private and public realms, a crucial area where Native Americans have for a long time nego-tiated change.

Figure 1 .

 1 Figure 1. Dedication of Standing Rock Monument, Fort Yates, North Dakota, 1886. Photo by D. F. Barry. Courtesy of the Denver Public Library Western History Collection, B-753.

  Notes 1 A. B. Welch, "Sitting Crow's Story about the Standing Rock," Native American Sacred Stones and Holy Places Described by Col. A. B. Welch, www.welchdakotapapers.com/2011/12/sacred-stones-and -holy-places/ (accessed 9 May 2017); Melvin R. Gilmore, "Making Records of Ancient Rituals of the Arikara Tribe in North Dakota," Gilmore Papers, American Indian Studies Research Institute, Bloomington, IN, p. 4, www .indiana.edu/~aisri/projects/gilmore.html (accessed 9 May 2017). 2 On Sioux' admiration for non-Dakota medicine men, see Ella C. Deloria, "Religion among the Dakotas," Dakota Ethnography: box 2, Ella Deloria Archives, http://zia.aisri.indiana.edu/deloria_archive/.