OpenASIP 2.2
Loading...
Searching...
No Matches
ConnectionSweeper.cc
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2011 Tampere University.
3
4 This file is part of TTA-Based Codesign Environment (TCE).
5
6 Permission is hereby granted, free of charge, to any person obtaining a
7 copy of this software and associated documentation files (the "Software"),
8 to deal in the Software without restriction, including without limitation
9 the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 and/or sell copies of the Software, and to permit persons to whom the
11 Software is furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in
14 all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 DEALINGS IN THE SOFTWARE.
23 */
24/**
25 * @file ConnectionSweeper.cc
26 *
27 * Explorer plugin that optimizes the interconnection network by
28 * removing connections with least effect to the cycle count.
29 *
30 * @author Pekka Jääskeläinen 2011
31 * @note rating: red
32 */
33
34#include <vector>
35#include <string>
36#include <set>
37#include <memory>
38
41#include "DSDBManager.hh"
42#include "Machine.hh"
43#include "Connection.hh"
44#include "TestApplication.hh"
45#include "Program.hh"
46#include "Instruction.hh"
47#include "Move.hh"
48#include "Port.hh"
49#include "FUPort.hh"
50#include "Socket.hh"
51#include "Terminal.hh"
52#include "Terminal.hh"
53#include "HDBRegistry.hh"
55#include "ControlUnit.hh"
56#include "HWOperation.hh"
57#include "StringTools.hh"
58#include "Segment.hh"
59#include "CostEstimates.hh"
60#include "Application.hh"
61#include "Exception.hh"
62#include "Procedure.hh"
63
64#include "LLVMBackend.hh"
66
67#include "MinimalOpSetCheck.hh"
69
70#include "tce_config.h"
71
72using namespace TTAProgram;
73using namespace TTAMachine;
74using namespace HDB;
75using std::endl;
76
77/**
78 * Explorer plugin that optimizes the interconnection network by
79 * removing connections with least effect to the cycle count first.
80 *
81 * 1) Sweeps through the buses in order.
82 * 2) For each bus, tries to remove each connection one-by-one,
83 * and evaluates the effect to the cycle count. The one with
84 * the least effect is removed first. The process is repeated
85 * until the minimum cycle count increase crosses an user-defined
86 * threshold, or the program becomes unschedulable.
87 * Emphasize RF port connections as they tend to get to the longest
88 * path due to the register selection logic being in the same path.
89 * 3) After that, the next bus is tried similarly, until either all
90 * the buses have been optimized this way.
91 * 4) The DSDB can be queried with the connection count as the first measure,
92 * the cycle count the second with both as small as possible.
93 *
94 */
97 "Optimizes the IC of the given configuration by removing bus "
98 "connections with least effect to the cycle count first.");
99
101
103 "Limit the reduction when the cycle count "
104 "drops more than this limit (%).");
105 addParameter(allOrNothingPN_, BOOL, false, "true",
106 "Do not consider single connections. Just try to remove "
107 "all of the bypass or RF connections at once. If fails, "
108 "leave them all. Leads quicker to symmetric reduced "
109 "connectivity machines.");
110 }
111
112 virtual bool requiresStartingPointArchitecture() const { return true; }
113 virtual bool producesArchitecture() const { return true; }
114 virtual bool requiresHDB() const { return false; }
115 virtual bool requiresSimulationData() const { return true; }
116
117 virtual std::vector<RowID>
118 explore(const RowID& startPointConfigurationID, const unsigned int&) {
119
120
122
123 DSDBManager& dsdb = db();
125 dsdb.configuration(startPointConfigurationID);
126
127 // loads starting configuration
128 Machine* origMach = NULL;
129 origMach = dsdb.architecture(startConf.architectureID);
130 // get cycle counts for the original architecture for each app
131 std::set<RowID> appIds = dsdb.applicationIDs();
132 for (std::set<RowID>::const_iterator appI = appIds.begin();
133 appI != appIds.end(); ++appI) {
134 RowID appID = *appI;
135 if (!dsdb.hasCycleCount(appID, startConf.architectureID)) {
136 CostEstimates estimates;
137 bool success = evaluate(startConf, estimates, false);
138 if (!success) {
139 throw Exception(
140 __FILE__, __LINE__, __func__,
141 "Could not evaluate the starting point arch.");
142 }
143 }
144 assert(dsdb.hasCycleCount(appID, startConf.architectureID));
145 origCycles_[appID] =
146 dsdb.cycleCount(appID, startConf.architectureID);
147 TCEString s;
148 s << "app: " << appID << " original cycles: ";
149 s << origCycles_[appID] << " total connections: "
151 verboseLog(s);
152 }
153
154 std::vector<RowID> result;
155
156 // sweep through the buses, the register file connections first
157 // start from the biggest allowed worsening threshold to find
158 // the machines with minimal connections first
159 const int thresholdStep =
160 std::max(maxCcWorseningThreshold_ / 4, (unsigned)1);
164 std::max(0, (int)ccWorseningThreshold_ - thresholdStep)) {
165 TCEString s;
166 s << "### Testing max worsening threshold "
167 << ccWorseningThreshold_ << "% of "
168 << maxCcWorseningThreshold_ << "%";
169 verboseLog(s);
170
171 s = "### Reducing register file and immediate unit connections.";
172 verboseLog(s);
173 std::list<RowID> rfSweepResults =
174 sweepRFs(startPointConfigurationID);
175
176 if (rfSweepResults.size() == 0) break;
177
178 RowID bestFromRFSweep = rfSweepResults.front();
179 result.insert(result.begin(), bestFromRFSweep);
180
181 s = "### Reducing bypass connections.";
182 verboseLog(s);
183
184 std::list<RowID> bypassSweepResults =
185 sweepBypasses(bestFromRFSweep);
186 if (bypassSweepResults.size() == 0) break;
187
188 RowID bestFromBPSweep = rfSweepResults.front();
189 result.insert(result.begin(), bestFromBPSweep);
190 }
191 return result;
192 }
193
194 /**
195 * Sweeps the register file and immediate unit connections.
196 */
197 std::list<RowID>
198 sweepRFs(RowID startPointConfigurationID) {
199
201 db().configuration(startPointConfigurationID);
202
203 // loads starting configuration
204 Machine* mach = db().architecture(startConf.architectureID);
205 DSDBManager::MachineConfiguration bestConf = startConf;
206
207
208 std::list<RowID> result;
209 for (int busI = 0; busI < mach->busNavigator().count();
210 ++busI) {
211 const TTAMachine::Bus& bus = *mach->busNavigator().item(busI);
212
213 verboseLog(TCEString("considering bus ") + bus.name());
214
215 std::vector<const TTAMachine::Connection*> connections;
216 const TTAMachine::Segment& seg = *bus.segment(0);
217 for (int rfI = 0; rfI < mach->registerFileNavigator().count();
218 ++rfI) {
219 const TTAMachine::RegisterFile& rf =
220 *mach->registerFileNavigator().item(rfI);
221 for (int connI = 0; connI < seg.connectionCount();
222 ++connI) {
223 const TTAMachine::Connection& conn =
224 seg.connection(*seg.connection(connI));
225 for (int portI = 0; portI < conn.socket()->portCount();
226 ++portI) {
227 const TTAMachine::Port& port =
228 *conn.socket()->port(portI);
229 if (port.parentUnit() == &rf) {
230 connections.push_back(&conn);
231 }
232 }
233 }
234 }
235 for (int iuI = 0; iuI < mach->immediateUnitNavigator().count();
236 ++iuI) {
237 const TTAMachine::ImmediateUnit& iu =
238 *mach->immediateUnitNavigator().item(iuI);
239 for (int connI = 0; connI < seg.connectionCount();
240 ++connI) {
241 const TTAMachine::Connection& conn =
242 seg.connection(*seg.connection(connI));
243 for (int portI = 0; portI < conn.socket()->portCount();
244 ++portI) {
245 const TTAMachine::Port& port =
246 *conn.socket()->port(portI);
247 if (port.parentUnit() == &iu) {
248 connections.push_back(&conn);
249 }
250 }
251 }
252 }
253
254 std::list<RowID> newConfs = removeAllConnections(connections, bestConf);
255
256 if (!allOrNothing_ && newConfs.size() == 0) {
257 verboseLog("trying the connections one-by-one\n");
258 removeLeastNecessaryConnections(connections, bestConf);
259 }
260
261 if (newConfs.size() > 0) {
262 bestConf = db().configuration(newConfs.front());
263 for (std::list<RowID>::reverse_iterator i = newConfs.rbegin();
264 i != newConfs.rend(); ++i) {
265 result.insert(result.begin(), *i);
266 }
267 }
268 }
269 return result;
270 }
271
272 /**
273 * Sweeps the bypass connections, that is, everything else but the
274 * register file and immediate unit connections.
275 */
276 std::list<RowID>
277 sweepBypasses(RowID startPointConfigurationID) {
278
280 db().configuration(startPointConfigurationID);
281
282 // loads starting configuration
283 Machine* mach = db().architecture(startConf.architectureID);
284 DSDBManager::MachineConfiguration bestConf = startConf;
285
286 std::list<RowID> result;
287 for (int busI = 0; busI < mach->busNavigator().count();
288 ++busI) {
289 const TTAMachine::Bus& bus = *mach->busNavigator().item(busI);
290
291 verboseLog(TCEString("considering bus ") + bus.name());
292
293 std::vector<const TTAMachine::Connection*> connections;
294 const TTAMachine::Segment& seg = *bus.segment(0);
295 for (int connI = 0; connI < seg.connectionCount();
296 ++connI) {
297 const TTAMachine::Connection& conn =
298 seg.connection(*seg.connection(connI));
299 // check if the connection is to an IU or RF
300 bool rfConnection = false;
301 for (int rfI = 0; rfI < mach->registerFileNavigator().count();
302 ++rfI) {
303 const TTAMachine::RegisterFile& rf =
304 *mach->registerFileNavigator().item(rfI);
305 for (int portI = 0; portI < conn.socket()->portCount();
306 ++portI) {
307 const TTAMachine::Port& port =
308 *conn.socket()->port(portI);
309 if (port.parentUnit() == &rf) {
310 rfConnection = true;
311 break;
312 }
313 }
314
315 }
316 for (int iuI = 0;
317 !rfConnection &&
318 iuI < mach->immediateUnitNavigator().count();
319 ++iuI) {
320 const TTAMachine::ImmediateUnit& iu =
321 *mach->immediateUnitNavigator().item(iuI);
322 for (int portI = 0; portI < conn.socket()->portCount();
323 ++portI) {
324 const TTAMachine::Port& port =
325 *conn.socket()->port(portI);
326 if (port.parentUnit() == &iu) {
327 rfConnection = true;
328 break;
329 }
330 }
331 }
332 if (!rfConnection) connections.push_back(&conn);
333 }
334
335
336 std::list<RowID> newConfs = removeAllConnections(connections, bestConf);
337
338 if (!allOrNothing_ && newConfs.size() == 0) {
339 verboseLog("trying the connections one-by-one\n");
340 removeLeastNecessaryConnections(connections, bestConf);
341 }
342
343 if (newConfs.size() > 0) {
344 bestConf = db().configuration(newConfs.front());
345 for (std::list<RowID>::reverse_iterator i = newConfs.rbegin();
346 i != newConfs.rend(); ++i) {
347 result.insert(result.begin(), *i);
348 }
349 }
350 }
351 return result;
352 }
353
354
355private:
356 // cycle counts for the original architecture for each app
357 // RowID == application ID
358 std::map<RowID, ClockCycleCount> origCycles_;
359 // parameter name variables
360 static const std::string ccWorseningThresholdPN_;
361 static const std::string allOrNothingPN_;
362 // the max cycle count worsening threshold in percentages in comparison to
363 // the fully connected architecture
365 // the current threshold
367 // from the set of connections, tries to remove all of them or none
368 // should lead to quick results with relatively symmetric connectivity
369 // machines
371 /**
372 * Reads the parameters given to the plugin.
373 */
380
381 /**
382 * Computes the average cycle count worsening for the given processor
383 * configuration across all the explored applications.
384 */
385 float
387 float worsenings = 0.0f;
388 std::set<RowID> appIds = db().applicationIDs();
389 for (std::set<RowID>::const_iterator appI = appIds.begin();
390 appI != appIds.end(); ++appI) {
391 RowID appID = *appI;
393 db().configuration(confId);
394 if (!db().hasCycleCount(appID, conf.architectureID)) {
395 continue; /* the evaluation had failed */
396 }
397 int origCycles = origCycles_[appID];
398 int newCycles =
399 db().cycleCount(appID, conf.architectureID);
400 worsenings += 100.0*(newCycles - origCycles) / origCycles;
401 }
402 float avgWorsening = worsenings / appIds.size();
403 return avgWorsening;
404 }
405
406
407 std::list<RowID>
409 std::vector<const TTAMachine::Connection*> connections,
410 const DSDBManager::MachineConfiguration& startConf) {
411
412 std::list<RowID> results;
413
414#if (!defined(HAVE_CXX11) && !defined(HAVE_CXX0X))
415 std::auto_ptr<TTAMachine::Machine> currentMachine(
416 db().architecture(startConf.architectureID));
417#else
418 std::unique_ptr<TTAMachine::Machine> currentMachine(
419 db().architecture(startConf.architectureID));
420#endif
421
422 for (std::vector<const TTAMachine::Connection*>::iterator
423 connI = connections.begin(); connI != connections.end();
424 ++connI) {
425 const TTAMachine::Connection* conn = *connI;
426 removeConnection(*currentMachine, *conn);
427 }
428
430 conf.architectureID = db().addArchitecture(*currentMachine);
431 RowID confId = db().addConfiguration(conf);
432 conf = db().configuration(confId);
433 CostEstimates estimates;
434 bool success = evaluate(conf, estimates, false);
435 float worsening = averageWorsening(confId);
436 if (success) {
437#if (!defined(HAVE_CXX11) && !defined(HAVE_CXX0X))
438 std::auto_ptr<TTAMachine::Machine> arch
439 (db().architecture(
440 db().configuration(confId).architectureID));
441#else
442 std::unique_ptr<TTAMachine::Machine> arch
443 (db().architecture(
444 db().configuration(confId).architectureID));
445#endif
446
447
448 if (worsening <= ccWorseningThreshold_) {
449 results.push_back(confId);
450 TCEString s;
451 s << "removing all connections was within threshold: #"
452 << confId << " avg worsening: ";
453 s << (int)worsening << "% " << " total connections: "
455 verboseLog(s);
456 } else {
457 TCEString s;
458 s << "removing all connections was not within the "
459 << "threshold: #"
460 << confId << " avg worsening: ";
461 s << (int)worsening << "% " << " total connections: "
463 s << "\n";
464 verboseLog(s);
465 }
466 } else {
467 TCEString s;
468 s << "removing all connections led to unschedulable program\n";
469 verboseLog(s);
470 }
471 return results;
472 }
473
474 /**
475 * Removes the connections in the given set that affect the cycle count
476 * the least until the worsening threshold is reached or in case the
477 * program becomes uncompilable.
478 *
479 * @param tryAllFirst Tries to remove all connections first and if it
480 * the results fits in the cc threshold, does not try configuration with
481 * the listed connections.
482 */
483 std::list<RowID>
485 std::vector<const TTAMachine::Connection*> connections,
486 const DSDBManager::MachineConfiguration& startConf) {
487
488 std::list<RowID> results;
489 DSDBManager::MachineConfiguration bestConf = startConf;
490
491 bool couldRemove = true;
492 while (couldRemove) {
493 couldRemove = false;
494 const TTAMachine::Connection* mostUnneededConn = NULL;
495 float bestAvgccWorsening = 100.0;
496 TTAMachine::Machine* currentMachine =
497 db().architecture(bestConf.architectureID);
498 RowID bestConfInThisIteration = -1;
499 std::vector<const TTAMachine::Connection*>::iterator unneededPos =
500 connections.end();
501 // find the least affecting connection removal for this stage
502 for (std::vector<const TTAMachine::Connection*>::iterator
503 connI = connections.begin(); connI != connections.end();
504 ++connI) {
505 const TTAMachine::Connection* conn = *connI;
506
507 // compute the avgccWorsening
508 // check if it's the best found and if it's above the
509 // threshold
510 TTAMachine::Machine mach = *currentMachine;
511 removeConnection(mach, *conn);
512
514 conf.architectureID = db().addArchitecture(mach);
515 RowID confId = db().addConfiguration(conf);
516 bool success = evaluate(db().configuration(confId));
517
518 if (success) {
519 unsigned int avgWorsening =
520 (unsigned)averageWorsening(confId);
521 if (avgWorsening <= ccWorseningThreshold_ &&
522 avgWorsening < bestAvgccWorsening) {
523 mostUnneededConn = conn;
524 bestConfInThisIteration = confId;
525 unneededPos = connI;
526 bestAvgccWorsening = avgWorsening;
527 TCEString s;
528 s << "new config: #" << bestConfInThisIteration
529 << " avg worsening: ";
530 s << (int)bestAvgccWorsening << "% "
531 << " total connections: "
533 *db().architecture(
534 db().configuration(confId).architectureID));
535 verboseLog(s);
536 }
537 } else {
538 TCEString s;
539 s << "new config: #" << confId << " is unschedulable";
540 verboseLog(s);
541 }
542 }
543 if (mostUnneededConn != NULL) {
544 // more connections we remove while staying in the threshold,
545 // better the processor gets
546 bestConf = db().configuration(bestConfInThisIteration);
547 couldRemove = true;
548 connections.erase(unneededPos);
549 results.push_front(bestConfInThisIteration);
550 TCEString s;
551 s << "best config from this bus sweep: #"
552 << bestConfInThisIteration << " avg worsening: ";
553 s << (int)bestAvgccWorsening << "% " << " total connections: "
555 *db().architecture(bestConf.architectureID));
556 verboseLog(s);
557 }
558 }
559 return results;
560 }
561
562 void
564 TTAMachine::Machine& mach, const TTAMachine::Connection& connection) {
565 TTAMachine::Segment& segment =
566 *mach.busNavigator().item(connection.bus()->parentBus()->name())->
567 segment(0);
568
569 TTAMachine::Socket& socket =
570 *mach.socketNavigator().item(connection.socket()->name());
571
572 segment.detachSocket(socket);
573 }
574};
575
576// parameter names
577const std::string
578ConnectionSweeper::ccWorseningThresholdPN_("cc_worsening_threshold");
579const std::string
580ConnectionSweeper::allOrNothingPN_("all_or_nothing_mode");
581
582
#define verboseLog(text)
#define __func__
#define assert(condition)
int RowID
Type definition of row ID in relational databases.
Definition DBTypes.hh:37
#define EXPORT_DESIGN_SPACE_EXPLORER_PLUGIN(PLUGIN_NAME__)
#define UINT(OPERAND)
Definition OSAL.hh:313
#define BOOL()
std::list< RowID > removeLeastNecessaryConnections(std::vector< const TTAMachine::Connection * > connections, const DSDBManager::MachineConfiguration &startConf)
virtual bool requiresHDB() const
std::list< RowID > sweepBypasses(RowID startPointConfigurationID)
static const std::string ccWorseningThresholdPN_
static const std::string allOrNothingPN_
PLUGIN_DESCRIPTION("Optimizes the IC of the given configuration by removing bus " "connections with least effect to the cycle count first.")
void removeConnection(TTAMachine::Machine &mach, const TTAMachine::Connection &connection)
unsigned int ccWorseningThreshold_
std::list< RowID > sweepRFs(RowID startPointConfigurationID)
virtual bool producesArchitecture() const
std::map< RowID, ClockCycleCount > origCycles_
float averageWorsening(RowID confId)
virtual std::vector< RowID > explore(const RowID &startPointConfigurationID, const unsigned int &)
std::list< RowID > removeAllConnections(std::vector< const TTAMachine::Connection * > connections, const DSDBManager::MachineConfiguration &startConf)
unsigned int maxCcWorseningThreshold_
virtual bool requiresStartingPointArchitecture() const
virtual bool requiresSimulationData() const
RowID addArchitecture(const TTAMachine::Machine &mom)
TTAMachine::Machine * architecture(RowID id) const
ClockCycleCount cycleCount(RowID application, RowID architecture) const
std::set< RowID > applicationIDs() const
MachineConfiguration configuration(RowID id) const
bool hasCycleCount(RowID application, RowID architecture) const
RowID addConfiguration(const MachineConfiguration &conf)
void readOptionalParameter(const std::string paramName, T &param) const
void addParameter(TCEString name, ExplorerPluginParameterType type, bool compulsory=true, TCEString defaultValue="", TCEString description="")
virtual DSDBManager & db()
virtual bool evaluate(const DSDBManager::MachineConfiguration &configuration, CostEstimates &results=dummyEstimate_, bool estimate=false)
static int totalConnectionCount(const TTAMachine::Machine &mach)
virtual Segment * segment(int index) const
Definition Bus.cc:329
virtual TCEString name() const
Socket * socket() const
Segment * bus() const
ComponentType * item(int index) const
virtual RegisterFileNavigator registerFileNavigator() const
Definition Machine.cc:450
virtual SocketNavigator socketNavigator() const
Definition Machine.cc:368
virtual ImmediateUnitNavigator immediateUnitNavigator() const
Definition Machine.cc:416
virtual BusNavigator busNavigator() const
Definition Machine.cc:356
Unit * parentUnit() const
void detachSocket(Socket &socket)
Definition Segment.cc:210
const Connection & connection(const Socket &socket) const
Definition Segment.cc:250
int connectionCount() const
Bus * parentBus() const
Port * port(int index) const
Definition Socket.cc:266