~elmer-csc-ubuntu/elmercsc/devel

printf("Partitions-N2: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));

for (pass=0; pass<niter; pass++) {

iset(nvtxs, -1, moved);

rpqReset(queues[0]);

rpqReset(queues[1]);

mincutorder = -1;

initcut = mincut = graph->mincut;

nbnd = graph->nbnd;

/* use the swaps array in place of the traditional perm array to save memory */

irandArrayPermute(nbnd, swaps, nbnd, 1);

for (ii=0; ii<nbnd; ii++) {

i = bndind[swaps[ii]];

ASSERT(where[i] == 2);

rpqInsert(queues[0], i, vwgt[i]-rinfo[i].edegrees[1]);

rpqInsert(queues[1], i, vwgt[i]-rinfo[i].edegrees[0]);

}

ASSERT(CheckNodeBnd(graph, nbnd));

ASSERT(CheckNodePartitionParams(graph));

limit = (ctrl->compress ? gk_min(5*nbnd, 400) : gk_min(2*nbnd, 300));

/******************************************************

* Get into the FM loop

*******************************************************/

mptr[0] = nmind = 0;

mindiff = iabs(pwgts[0]-pwgts[1]);

to = (pwgts[0] < pwgts[1] ? 0 : 1);

for (nswaps=0; nswaps<nvtxs; nswaps++) {

u[0] = rpqSeeTopVal(queues[0]);

u[1] = rpqSeeTopVal(queues[1]);

if (u[0] != -1 && u[1] != -1) {

g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];

g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];

to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2));

if (pwgts[to]+vwgt[u[to]] > badmaxpwgt)

100

to = (to+1)%2;

101

}

102

else if (u[0] == -1 && u[1] == -1) {

103

break;

104

}

105

else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {

106

to = 0;

107

}

108

else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {

109

to = 1;

110

}

111

else

112

break;

113

114

other = (to+1)%2;

115

116

higain = rpqGetTop(queues[to]);

117

if (moved[higain] == -1) /* Delete if it was in the separator originally */

118

rpqDelete(queues[other], higain);

119

120

ASSERT(bndptr[higain] != -1);

121

122

/* The following check is to ensure we break out if there is a posibility

123

of over-running the mind array. */

124

if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)

125

break;

126

127

pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);

128

129

newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));

130

if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {

131

mincut = pwgts[2];

132

mincutorder = nswaps;

133

mindiff = newdiff;

134

}

135

else {

136

if (nswaps - mincutorder > 2*limit ||

137

(nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {

138

pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);

139

break; /* No further improvement, break out */

140

}

141

}

142

143

BNDDelete(nbnd, bndind, bndptr, higain);

144

pwgts[to] += vwgt[higain];

145

where[higain] = to;

146

moved[higain] = nswaps;

147

swaps[nswaps] = higain;

148

149

150

/**********************************************************

151

* Update the degrees of the affected nodes

152

***********************************************************/

153

for (j=xadj[higain]; j<xadj[higain+1]; j++) {

154

k = adjncy[j];

155

if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */

156

oldgain = vwgt[k]-rinfo[k].edegrees[to];

157

rinfo[k].edegrees[to] += vwgt[higain];

158

if (moved[k] == -1 || moved[k] == -(2+other))

159

rpqUpdate(queues[other], k, oldgain-vwgt[higain]);

160

}

161

else if (where[k] == other) { /* This vertex is pulled into the separator */

162

ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));

163

BNDInsert(nbnd, bndind, bndptr, k);

164

165

mind[nmind++] = k; /* Keep track for rollback */

166

where[k] = 2;

167

pwgts[other] -= vwgt[k];

168

169

edegrees = rinfo[k].edegrees;

170

edegrees[0] = edegrees[1] = 0;

171

for (jj=xadj[k]; jj<xadj[k+1]; jj++) {

172

kk = adjncy[jj];

173

if (where[kk] != 2)

174

edegrees[where[kk]] += vwgt[kk];

175

else {

176

oldgain = vwgt[kk]-rinfo[kk].edegrees[other];

177

rinfo[kk].edegrees[other] -= vwgt[k];

178

if (moved[kk] == -1 || moved[kk] == -(2+to))

179

rpqUpdate(queues[to], kk, oldgain+vwgt[k]);

180

}

181

}

182

183

/* Insert the new vertex into the priority queue. Only one side! */

184

if (moved[k] == -1) {

185

rpqInsert(queues[to], k, vwgt[k]-edegrees[other]);

186

moved[k] = -(2+to);

187

}

188

}

189

}

190

mptr[nswaps+1] = nmind;

191

192

IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,

193

printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] [%4"PRIDX" %4"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));

194

195

}

196

197

198

/****************************************************************

199

* Roll back computation

200

*****************************************************************/

201

for (nswaps--; nswaps>mincutorder; nswaps--) {

202

higain = swaps[nswaps];

203

204

ASSERT(CheckNodePartitionParams(graph));

205

206

to = where[higain];

207

other = (to+1)%2;

208

INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);

209

where[higain] = 2;

210

BNDInsert(nbnd, bndind, bndptr, higain);

211

212

edegrees = rinfo[higain].edegrees;

213

edegrees[0] = edegrees[1] = 0;

214

for (j=xadj[higain]; j<xadj[higain+1]; j++) {

215

k = adjncy[j];

216

if (where[k] == 2)

217

rinfo[k].edegrees[to] -= vwgt[higain];

218

else

219

edegrees[where[k]] += vwgt[k];

220

}

221

222

/* Push nodes out of the separator */

223

for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {

224

k = mind[j];

225

ASSERT(where[k] == 2);

226

where[k] = other;

227

INC_DEC(pwgts[other], pwgts[2], vwgt[k]);

228

BNDDelete(nbnd, bndind, bndptr, k);

229

for (jj=xadj[k]; jj<xadj[k+1]; jj++) {

230

kk = adjncy[jj];

231

if (where[kk] == 2)

232

rinfo[kk].edegrees[other] += vwgt[k];

233

}

234

}

235

}

236

237

ASSERT(mincut == pwgts[2]);

238

239

IFSET(ctrl->dbglvl, METIS_DBG_REFINE,

240

printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));

241

242

graph->mincut = mincut;

243

graph->nbnd = nbnd;

244

245

if (mincutorder == -1 || mincut >= initcut)

246

break;

247

}

248

249

rpqDestroy(queues[0]);

250

rpqDestroy(queues[1]);

251

252

WCOREPOP;

253

}

254

255

256

/*************************************************************************/

257

/*! This function performs a node-based FM refinement.

258

Each refinement iteration is split into two sub-iterations.

259

In each sub-iteration only moves to one of the left/right partitions

260

is allowed; hence, it is one-sided.

261

262

/**************************************************************************/

263

void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter)

264

{

265

idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind, iend;

266

idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;

267

idx_t *mptr, *mind, *swaps;

268

rpq_t *queue;

269

nrinfo_t *rinfo;

270

idx_t higain, mincut, initcut, mincutorder;

271

idx_t pass, to, other, limit;

272

idx_t badmaxpwgt, mindiff, newdiff;

273

real_t mult;

274

275

WCOREPUSH;

276

277

nvtxs = graph->nvtxs;

278

xadj = graph->xadj;

279

adjncy = graph->adjncy;

280

vwgt = graph->vwgt;

281

282

bndind = graph->bndind;

283

bndptr = graph->bndptr;

284

where = graph->where;

285

pwgts = graph->pwgts;

286

rinfo = graph->nrinfo;

287

288

queue = rpqCreate(nvtxs);

289

290

swaps = iwspacemalloc(ctrl, nvtxs);

291

mptr = iwspacemalloc(ctrl, nvtxs+1);

292

mind = iwspacemalloc(ctrl, 2*nvtxs);

293

294

mult = 0.5*ctrl->ubfactors[0];

295

badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));

296

297

IFSET(ctrl->dbglvl, METIS_DBG_REFINE,

298

printf("Partitions-N1: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));

299

300

to = (pwgts[0] < pwgts[1] ? 1 : 0);

301

for (pass=0; pass<2*niter; pass++) { /* the 2*niter is for the two sides */

302

other = to;

303

to = (to+1)%2;

304

305

rpqReset(queue);

306

307

mincutorder = -1;

308

initcut = mincut = graph->mincut;

309

nbnd = graph->nbnd;

310

311

/* use the swaps array in place of the traditional perm array to save memory */

312

irandArrayPermute(nbnd, swaps, nbnd, 1);

313

for (ii=0; ii<nbnd; ii++) {

314

i = bndind[swaps[ii]];

315

ASSERT(where[i] == 2);

316

rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);

317

}

318

319

ASSERT(CheckNodeBnd(graph, nbnd));

320

ASSERT(CheckNodePartitionParams(graph));

321

322

limit = (ctrl->compress ? gk_min(5*nbnd, 500) : gk_min(3*nbnd, 300));

323

324

/******************************************************

325

* Get into the FM loop

326

*******************************************************/

327

IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux3Tmr));

328

mptr[0] = nmind = 0;

329

mindiff = iabs(pwgts[0]-pwgts[1]);

330

for (nswaps=0; nswaps<nvtxs; nswaps++) {

331

if ((higain = rpqGetTop(queue)) == -1)

332

break;

333

334

ASSERT(bndptr[higain] != -1);

335

336

/* The following check is to ensure we break out if there is a posibility

337

of over-running the mind array. */

338

if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)

339

break;

340

341

if (pwgts[to]+vwgt[higain] > badmaxpwgt)

342

break; /* No point going any further. Balance will be bad */

343

344

pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);

345

346

newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));

347

if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {

348

mincut = pwgts[2];

349

mincutorder = nswaps;

350

mindiff = newdiff;

351

}

352

else {

353

if (nswaps - mincutorder > 3*limit ||

354

(nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {

355

pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);

356

break; /* No further improvement, break out */

357

}

358

}

359

360

BNDDelete(nbnd, bndind, bndptr, higain);

361

pwgts[to] += vwgt[higain];

362

where[higain] = to;

363

swaps[nswaps] = higain;

364

365

366

/**********************************************************

367

* Update the degrees of the affected nodes

368

***********************************************************/

369

IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux1Tmr));

370

for (j=xadj[higain]; j<xadj[higain+1]; j++) {

371

k = adjncy[j];

372

373

if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */

374

rinfo[k].edegrees[to] += vwgt[higain];

375

}

376

else if (where[k] == other) { /* This vertex is pulled into the separator */

377

ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));

378

BNDInsert(nbnd, bndind, bndptr, k);

379

380

mind[nmind++] = k; /* Keep track for rollback */

381

where[k] = 2;

382

pwgts[other] -= vwgt[k];

383

384

edegrees = rinfo[k].edegrees;

385

edegrees[0] = edegrees[1] = 0;

386

for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {

387

kk = adjncy[jj];

388

if (where[kk] != 2)

389

edegrees[where[kk]] += vwgt[kk];

390

else {

391

rinfo[kk].edegrees[other] -= vwgt[k];

392

393

/* Since the moves are one-sided this vertex has not been moved yet */

394

rpqUpdate(queue, kk, vwgt[kk]-rinfo[kk].edegrees[other]);

395

}

396

}

397

398

/* Insert the new vertex into the priority queue. Safe due to one-sided moves */

399

rpqInsert(queue, k, vwgt[k]-edegrees[other]);

400

}

401

}

402

mptr[nswaps+1] = nmind;

403

IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux1Tmr));

404

405

406

IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,

407

printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"] [%3"PRIDX" %2"PRIDX"]\n",

408

higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain],

409

pwgts[0], pwgts[1], pwgts[2], nswaps, limit));

410

}

411

IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux3Tmr));

412

413

414

/****************************************************************

415

* Roll back computation

416

*****************************************************************/

417

IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->Aux2Tmr));

418

for (nswaps--; nswaps>mincutorder; nswaps--) {

419

higain = swaps[nswaps];

420

421

ASSERT(CheckNodePartitionParams(graph));

422

ASSERT(where[higain] == to);

423

424

INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);

425

where[higain] = 2;

426

BNDInsert(nbnd, bndind, bndptr, higain);

427

428

edegrees = rinfo[higain].edegrees;

429

edegrees[0] = edegrees[1] = 0;

430

for (j=xadj[higain]; j<xadj[higain+1]; j++) {

431

k = adjncy[j];

432

if (where[k] == 2)

433

rinfo[k].edegrees[to] -= vwgt[higain];

434

else

435

edegrees[where[k]] += vwgt[k];

436

}

437

438

/* Push nodes out of the separator */

439

for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {

440

k = mind[j];

441

ASSERT(where[k] == 2);

442

where[k] = other;

443

INC_DEC(pwgts[other], pwgts[2], vwgt[k]);

444

BNDDelete(nbnd, bndind, bndptr, k);

445

for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {

446

kk = adjncy[jj];

447

if (where[kk] == 2)

448

rinfo[kk].edegrees[other] += vwgt[k];

449

}

450

}

451

}

452

IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->Aux2Tmr));

453

454

ASSERT(mincut == pwgts[2]);

455

456

IFSET(ctrl->dbglvl, METIS_DBG_REFINE,

457

printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));

458

459

graph->mincut = mincut;

460

graph->nbnd = nbnd;

461

462

if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))

463

break;

464

}

465

466

rpqDestroy(queue);

467

468

WCOREPOP;

469

}

470

471

472

/*************************************************************************/

473

/*! This function balances the left/right partitions of a separator

474

tri-section */

475

/*************************************************************************/

476

void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph)

477

{

478

idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, gain;

479

idx_t badmaxpwgt, higain, oldgain, pass, to, other;

480

idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;

481

idx_t *perm, *moved;

482

rpq_t *queue;

483

nrinfo_t *rinfo;

484

real_t mult;

485

486

nvtxs = graph->nvtxs;

487

xadj = graph->xadj;

488

adjncy = graph->adjncy;

489

vwgt = graph->vwgt;

490

491

bndind = graph->bndind;

492

bndptr = graph->bndptr;

493

where = graph->where;

494

pwgts = graph->pwgts;

495

rinfo = graph->nrinfo;

496

497

mult = 0.5*ctrl->ubfactors[0];

498

499

badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));

500

if (gk_max(pwgts[0], pwgts[1]) < badmaxpwgt)

501

return;

502

if (iabs(pwgts[0]-pwgts[1]) < 3*graph->tvwgt[0]/nvtxs)

503

return;

504

505

WCOREPUSH;

506

507

to = (pwgts[0] < pwgts[1] ? 0 : 1);

508

other = (to+1)%2;

509

510

queue = rpqCreate(nvtxs);

511

512

perm = iwspacemalloc(ctrl, nvtxs);

513

moved = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));

514

515

IFSET(ctrl->dbglvl, METIS_DBG_REFINE,

516

printf("Partitions: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX" [B]\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));

517

518

nbnd = graph->nbnd;

519

irandArrayPermute(nbnd, perm, nbnd, 1);

520

for (ii=0; ii<nbnd; ii++) {

521

i = bndind[perm[ii]];

522

ASSERT(where[i] == 2);

523

rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);

524

}

525

526

ASSERT(CheckNodeBnd(graph, nbnd));

527

ASSERT(CheckNodePartitionParams(graph));

528

529

/******************************************************

530

* Get into the FM loop

531

*******************************************************/

532

for (nswaps=0; nswaps<nvtxs; nswaps++) {

533

if ((higain = rpqGetTop(queue)) == -1)

534

break;

535

536

moved[higain] = 1;

537

538

gain = vwgt[higain]-rinfo[higain].edegrees[other];

539

badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));

540

541

/* break if other is now underwight */

542

if (pwgts[to] > pwgts[other])

543

break;

544

545

/* break if balance is achieved and no +ve or zero gain */

546

if (gain < 0 && pwgts[other] < badmaxpwgt)

547

break;

548

549

/* skip this vertex if it will violate balance on the other side */

550

if (pwgts[to]+vwgt[higain] > badmaxpwgt)

551

continue;

552

553

ASSERT(bndptr[higain] != -1);

554

555

pwgts[2] -= gain;

556

557

BNDDelete(nbnd, bndind, bndptr, higain);

558

pwgts[to] += vwgt[higain];

559

where[higain] = to;

560

561

IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,

562

printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %3"PRIDX", \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));

563

564

565

/**********************************************************

566

* Update the degrees of the affected nodes

567

***********************************************************/

568

for (j=xadj[higain]; j<xadj[higain+1]; j++) {

569

k = adjncy[j];

570

if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */

571

rinfo[k].edegrees[to] += vwgt[higain];

572

}

573

else if (where[k] == other) { /* This vertex is pulled into the separator */

574

ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));

575

BNDInsert(nbnd, bndind, bndptr, k);

576

577

where[k] = 2;

578

pwgts[other] -= vwgt[k];

579

580

edegrees = rinfo[k].edegrees;

581

edegrees[0] = edegrees[1] = 0;

582

for (jj=xadj[k]; jj<xadj[k+1]; jj++) {

583

kk = adjncy[jj];

584

if (where[kk] != 2)

585

edegrees[where[kk]] += vwgt[kk];

586

else {

587

ASSERT(bndptr[kk] != -1);

588

oldgain = vwgt[kk]-rinfo[kk].edegrees[other];

589

rinfo[kk].edegrees[other] -= vwgt[k];

590

591

if (moved[kk] == -1)

592

rpqUpdate(queue, kk, oldgain+vwgt[k]);

593

}

594

}

595

596

/* Insert the new vertex into the priority queue */

597

rpqInsert(queue, k, vwgt[k]-edegrees[other]);

598

}

599

}

600

}

601

602

IFSET(ctrl->dbglvl, METIS_DBG_REFINE,

603

printf("\tBalanced sep: %6"PRIDX" at %4"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", pwgts[2], nswaps, pwgts[0], pwgts[1], nbnd));

604

605

graph->mincut = pwgts[2];

606

graph->nbnd = nbnd;

607

608

rpqDestroy(queue);

609

610

WCOREPOP;

611

}

612

Older »