1 /***************************************************************************
2 * include/stxxl/bits/algo/async_schedule.h
3 *
4 * Part of the STXXL. See http://stxxl.sourceforge.net
5 *
6 * Copyright (C) 2002 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7 * Copyright (C) 2009 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
8 *
9 * Distributed under the Boost Software License, Version 1.0.
10 * (See accompanying file LICENSE_1_0.txt or copy at
11 * http://www.boost.org/LICENSE_1_0.txt)
12 **************************************************************************/
13
14 #ifndef STXXL_ALGO_ASYNC_SCHEDULE_HEADER
15 #define STXXL_ALGO_ASYNC_SCHEDULE_HEADER
16
17 // Implements the "prudent prefetching" as described in
18 // D. Hutchinson, P. Sanders, J. S. Vitter: Duality between prefetching
19 // and queued writing on parallel disks, 2005
20 // DOI: 10.1137/S0097539703431573
21
22 #include <stxxl/bits/common/types.h>
23 #include <stxxl/bits/common/simple_vector.h>
24 #include <stxxl/bits/namespace.h>
25
26 STXXL_BEGIN_NAMESPACE
27
28 void compute_prefetch_schedule(
29 const int_type* first,
30 const int_type* last,
31 int_type* out_first,
32 int_type m,
33 int_type D);
34
compute_prefetch_schedule(int_type * first,int_type * last,int_type * out_first,int_type m,int_type D)35 inline void compute_prefetch_schedule(
36 int_type* first,
37 int_type* last,
38 int_type* out_first,
39 int_type m,
40 int_type D)
41 {
42 compute_prefetch_schedule(static_cast<const int_type*>(first), last, out_first, m, D);
43 }
44
45 template <typename RunType>
compute_prefetch_schedule(const RunType & input,int_type * out_first,int_type m,int_type D)46 void compute_prefetch_schedule(
47 const RunType& input,
48 int_type* out_first,
49 int_type m,
50 int_type D)
51 {
52 const int_type L = input.size();
53 simple_vector<int_type> disks(L);
54 for (int_type i = 0; i < L; ++i)
55 disks[i] = input[i].bid.storage->get_device_id();
56 compute_prefetch_schedule(disks.begin(), disks.end(), out_first, m, D);
57 }
58
59 template <typename BidIteratorType>
compute_prefetch_schedule(BidIteratorType input_begin,BidIteratorType input_end,int_type * out_first,int_type m,int_type D)60 void compute_prefetch_schedule(
61 BidIteratorType input_begin,
62 BidIteratorType input_end,
63 int_type* out_first,
64 int_type m,
65 int_type D)
66 {
67 const int_type L = input_end - input_begin;
68 simple_vector<int_type> disks(L);
69 int_type i = 0;
70 for (BidIteratorType it = input_begin; it != input_end; ++it, ++i)
71 disks[i] = it->storage->get_device_id();
72 compute_prefetch_schedule(disks.begin(), disks.end(), out_first, m, D);
73 }
74
75 STXXL_END_NAMESPACE
76
77 #endif // !STXXL_ALGO_ASYNC_SCHEDULE_HEADER
78 // vim: et:ts=4:sw=4
79