STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
async_schedule.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * lib/algo/async_schedule.cpp
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002, 2009 Roman Dementiev <[email protected]>
7  * Copyright (C) 2009, 2010 Andreas Beckmann <[email protected]>
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 // Implements the "prudent prefetching" as described in
15 // D. Hutchinson, P. Sanders, J. S. Vitter: Duality between prefetching
16 // and queued writing on parallel disks, 2005
17 // DOI: 10.1137/S0097539703431573
18 
22 #include <stxxl/bits/io/file.h>
23 #include <stxxl/bits/namespace.h>
24 #include <stxxl/bits/parallel.h>
25 #include <stxxl/bits/unused.h>
26 #include <stxxl/bits/verbose.h>
27 
28 #include <algorithm>
29 #include <cassert>
30 #include <functional>
31 #include <queue>
32 #include <utility>
33 #include <vector>
34 
36 
37 namespace async_schedule_local {
38 
39 // only one type of event: WRITE COMPLETED
40 struct sim_event
41 {
43  int_type iblock;
44  inline sim_event(int_type t, int_type b) : timestamp(t), iblock(b) { }
45 };
46 
47 struct sim_event_cmp : public std::binary_function<sim_event, sim_event, bool>
48 {
49  inline bool operator () (const sim_event& a, const sim_event& b) const
50  {
51  return a.timestamp > b.timestamp;
52  }
53 };
54 
55 typedef std::pair<int_type, int_type> write_time_pair;
56 struct write_time_cmp : public std::binary_function<write_time_pair, write_time_pair, bool>
57 {
58  inline bool operator () (const write_time_pair& a, const write_time_pair& b) const
59  {
60  return a.second > b.second;
61  }
62 };
63 
64 static inline int_type get_disk(int_type i, const int_type* disks, int_type D)
65 {
66  int_type disk = disks[i];
67  if (disk == (int_type)file::DEFAULT_DEVICE_ID)
68  disk = D; // remap to sentinel
69  assert(0 <= disk && disk <= D);
70  return disk;
71 }
72 
74  const int_type* disks,
75  const int_type L,
76  const int_type m_init,
77  const int_type D,
78  std::pair<int_type, int_type>* o_time)
79 {
80  typedef std::priority_queue<sim_event, std::vector<sim_event>, sim_event_cmp> event_queue_type;
81  typedef std::queue<int_type> disk_queue_type;
82  assert(L >= D);
83  simple_vector<disk_queue_type> disk_queues(D + 1); // + sentinel for remapping NO_ALLOCATOR
84  event_queue_type event_queue;
85 
86  int_type m = m_init;
87  int_type i = L - 1;
88  int_type oldtime = 0;
89  simple_vector<bool> disk_busy(D + 1);
90 
91  while (m && (i >= 0))
92  {
93  int_type disk = get_disk(i, disks, D);
94  disk_queues[disk].push(i);
95  i--;
96  m--;
97  }
98 
99  for (int_type ii = 0; ii <= D; ii++)
100  if (!disk_queues[ii].empty())
101  {
102  int_type j = disk_queues[ii].front();
103  disk_queues[ii].pop();
104  event_queue.push(sim_event(1, j));
105  //STXXL_MSG("Block "<<j<<" scheduled");
106  }
107 
108  while (!event_queue.empty())
109  {
110  sim_event cur = event_queue.top();
111  event_queue.pop();
112  if (oldtime != cur.timestamp)
113  {
114  // clear disk_busy
115  for (int_type j = 0; j <= D; j++)
116  disk_busy[j] = false;
117 
118  oldtime = cur.timestamp;
119  }
120 
121  STXXL_VERBOSE1("Block " << cur.iblock << " put out, time " << cur.timestamp << " disk: " << disks[cur.iblock]);
122  o_time[cur.iblock] = std::pair<int_type, int_type>(cur.iblock, cur.timestamp);
123 
124  if (i >= 0)
125  {
126  int_type disk = get_disk(i, disks, D);
127  if (disk_busy[disk])
128  {
129  disk_queues[disk].push(i--);
130  }
131  else
132  {
133  if (!disk_queues[disk].empty())
134  {
135  STXXL_VERBOSE1("c Block " << disk_queues[disk].front() << " scheduled for time " << cur.timestamp + 1);
136  event_queue.push(sim_event(cur.timestamp + 1, disk_queues[disk].front()));
137  disk_queues[disk].pop();
138  }
139  else
140  {
141  STXXL_VERBOSE1("a Block " << i << " scheduled for time " << cur.timestamp + 1);
142  event_queue.push(sim_event(cur.timestamp + 1, i--));
143  }
144  disk_busy[disk] = true;
145  }
146  }
147 
148  // add next block to write
149  int_type disk = get_disk(cur.iblock, disks, D);
150  if (!disk_busy[disk] && !disk_queues[disk].empty())
151  {
152  STXXL_VERBOSE1("b Block " << disk_queues[disk].front() << " scheduled for time " << cur.timestamp + 1);
153  event_queue.push(sim_event(cur.timestamp + 1, disk_queues[disk].front()));
154  disk_queues[disk].pop();
155  disk_busy[disk] = true;
156  }
157  }
158 
159  assert(i == -1);
160  for (int_type j = 0; j <= D; j++)
161  assert(disk_queues[j].empty());
162 
163  return (oldtime - 1);
164 }
165 
166 } // namespace async_schedule_local
167 
169  const int_type* first,
170  const int_type* last,
171  int_type* out_first,
172  int_type m,
173  int_type D)
174 {
175  typedef std::pair<int_type, int_type> pair_type;
176  int_type L = last - first;
177  if (L <= D)
178  {
179  for (int_type i = 0; i < L; ++i)
180  out_first[i] = i;
181 
182  return;
183  }
184  pair_type* write_order = new pair_type[L];
185 
186  int_type w_steps = async_schedule_local::simulate_async_write(first, L, m, D, write_order);
187 
188  STXXL_VERBOSE1("Write steps: " << w_steps);
189 
190  for (int_type i = 0; i < L; i++)
191  STXXL_VERBOSE1(first[i] << " " << write_order[i].first << " " << write_order[i].second);
192 
193  std::stable_sort(write_order, write_order + L, async_schedule_local::write_time_cmp() _STXXL_FORCE_SEQUENTIAL);
194 
195  for (int_type i = 0; i < L; i++)
196  {
197  out_first[i] = write_order[i].first;
198  //if(out_first[i] != i)
199  STXXL_VERBOSE1(i << " " << out_first[i]);
200  }
201 
202  delete[] write_order;
203  STXXL_UNUSED(w_steps);
204 }
205 
207 
208 // vim: et:ts=4:sw=4
std::pair< int_type, int_type > write_time_pair
Encapsulates disk queues.
Definition: disk_queues.h:37
static int_type get_disk(int_type i, const int_type *disks, int_type D)
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
void STXXL_UNUSED(const U &)
Definition: unused.h:22
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
int_type simulate_async_write(const int_type *disks, const int_type L, const int_type m_init, const int_type D, std::pair< int_type, int_type > *o_time)
Simpler non-growing vector without initialization.
Definition: simple_vector.h:39
double timestamp()
Returns number of seconds since the epoch, high resolution.
Definition: timer.h:44
void compute_prefetch_schedule(const int_type *first, const int_type *last, int_type *out_first, int_type m, int_type D)
#define _STXXL_FORCE_SEQUENTIAL
Definition: parallel.h:34
#define STXXL_END_NAMESPACE
Definition: namespace.h:17