place_qpsolver.c File Reference

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "place_qpsolver.h"

Include dependency graph for place_qpsolver.c:

Go to the source code of this file.

Macros
#define	QPS_TOL   1.0e-3
#define	QPS_EPS   (QPS_TOL * QPS_TOL)
#define	QPS_MAX_TOL   0.1
#define	QPS_LOOP_TOL   1.0e-3
#define	QPS_RELAX_ITER   180
#define	QPS_MAX_ITER   200
#define	QPS_STEPSIZE_RETRIES   2
#define	QPS_MINSTEP   1.0e-6
#define	QPS_DEC_CHANGE   0.01
#define	QPS_PRECON
#define	QPS_PRECON_EPS   1.0e-9

Functions
void	qps_init (qps_problem_t *p)
void	qps_solve (qps_problem_t *p)
void	qps_clean (qps_problem_t *p)

Macro Definition Documentation

QPS_DEC_CHANGE

#define QPS_DEC_CHANGE   0.01

Definition at line 32 of file place_qpsolver.c.

QPS_EPS

#define QPS_EPS   (QPS_TOL * QPS_TOL)

Definition at line 23 of file place_qpsolver.c.

QPS_LOOP_TOL

#define QPS_LOOP_TOL   1.0e-3

Definition at line 26 of file place_qpsolver.c.

QPS_MAX_ITER

#define QPS_MAX_ITER   200

Definition at line 29 of file place_qpsolver.c.

QPS_MAX_TOL

#define QPS_MAX_TOL   0.1

Definition at line 25 of file place_qpsolver.c.

QPS_MINSTEP

#define QPS_MINSTEP   1.0e-6

Definition at line 31 of file place_qpsolver.c.

QPS_PRECON

#define QPS_PRECON

Definition at line 34 of file place_qpsolver.c.

QPS_PRECON_EPS

#define QPS_PRECON_EPS   1.0e-9

Definition at line 35 of file place_qpsolver.c.

QPS_RELAX_ITER

#define QPS_RELAX_ITER   180

Definition at line 28 of file place_qpsolver.c.

QPS_STEPSIZE_RETRIES

#define QPS_STEPSIZE_RETRIES   2

Definition at line 30 of file place_qpsolver.c.

QPS_TOL

#define QPS_TOL   1.0e-3

Definition at line 22 of file place_qpsolver.c.

Function Documentation

qps_clean()

void qps_clean

(

qps_problem_t *

p

)

Definition at line 1259 of file place_qpsolver.c.

{
  free(p->priv_tp);
  free(p->priv_ii);
  free(p->priv_cc);
  free(p->priv_cr);
  free(p->priv_cw);
  free(p->priv_ct);
 
#if defined(QPS_DEBUG)
  fclose(p->priv_fp);
#endif /* QPS_DEBUG */
}

Here is the call graph for this function:

Here is the caller graph for this function:

qps_init()

void qps_init

(

qps_problem_t *

p

)

Definition at line 542 of file place_qpsolver.c.

{
  int i, j;
  int pr, pw;
 
#if defined(QPS_DEBUG)
  p->priv_fp = fopen(QPS_DEBUG_FILE, "a");
  assert(p->priv_fp);
#endif
 
#if (QPS_DEBUG > 5)
  fprintf(p->priv_fp, "### n=%d gn=%d ln=%d\n", p->num_cells, p->cog_num,
      p->loop_num);
  pr = 0;
  fprintf(p->priv_fp, "### (c w) values\n");
  for (i = 0; i < p->num_cells; i++) {
    fprintf(p->priv_fp, "net %d: ", i);
    while (p->connect[pr] >= 0) {
      fprintf(p->priv_fp, "(%d %f) ", p->connect[pr], p->edge_weight[pr]);
      pr++;
    }
    fprintf(p->priv_fp, "(-1 -1.0)\n");
    pr++;
  }
  fprintf(p->priv_fp, "### (x y f) values\n");
  for (i = 0; i < p->num_cells; i++) {
    fprintf(p->priv_fp, "cell %d: (%f %f %d)\n", i, p->x[i], p->y[i],
        p->fixed[i]);
  }
#if 0
  if (p->cog_num) {
    fprintf(p->priv_fp, "### ga values\n");
    for (i = 0; i < p->num_cells; i++) {
      fprintf(p->priv_fp, "cell %d: (%f)\n", i, p->area[i]);
    }
  }
  pr = 0;
  fprintf(p->priv_fp, "### gl values\n");
  for (i = 0; i < p->cog_num; i++) {
    fprintf(p->priv_fp, "cog %d: ", i);
    while (p->cog_list[pr] >= 0) {
      fprintf(p->priv_fp, "%d ", p->cog_list[pr]);
      pr++;
    }
    fprintf(p->priv_fp, "-1\n");
    pr++;
  }
  fprintf(p->priv_fp, "### (gx gy) values\n");
  for (i = 0; i < p->cog_num; i++) {
    fprintf(p->priv_fp, "cog %d: (%f %f)\n", i, p->cog_x[i], p->cog_y[i]);
  }
#endif
#endif /* QPS_DEBUG */
 
  p->priv_ii = (int *)malloc(p->num_cells * sizeof(int));
  assert(p->priv_ii);
 
  p->max_enable = 0;
 
  p->priv_fopt = 0.0;
 
  /* canonify c and w */
  pr = pw = 0;
  for (i = 0; i < p->num_cells; i++) {
    while ((j = p->connect[pr]) >= 0) {
      if (j > i) {
    pw++;
      }
      pr++;
    }
    pw++;
    pr++;
  }
  p->priv_cc = (int *)malloc(pw * sizeof(int));
  assert(p->priv_cc);
  p->priv_cr = (int *)malloc(p->num_cells * sizeof(int));
  assert(p->priv_cr);
  p->priv_cw = (qps_float_t*)malloc(pw * sizeof(qps_float_t));
  assert(p->priv_cw);
  p->priv_ct = (qps_float_t*)malloc(pw * sizeof(qps_float_t));
  assert(p->priv_ct);
  p->priv_cm = pw;
  pr = pw = 0;
  for (i = 0; i < p->num_cells; i++) {
    p->priv_cr[i] = pw;
    while ((j = p->connect[pr]) >= 0) {
      if (j > i) {
    p->priv_cc[pw] = p->connect[pr];
    p->priv_ct[pw] = p->edge_weight[pr];
    pw++;
      }
      pr++;
    }
    p->priv_cc[pw] = -1;
    p->priv_ct[pw] = -1.0;
    pw++;
    pr++;
  }
  assert(pw == p->priv_cm);
 
  /* temp arrays for function eval */
  p->priv_tp = (qps_float_t *) malloc(4 * p->num_cells * sizeof(qps_float_t));
  assert(p->priv_tp);
  p->priv_tp2 = p->priv_tp + 2 * p->num_cells;
}

Here is the call graph for this function:

Here is the caller graph for this function:

qps_solve()

void qps_solve

(

qps_problem_t *

p

)

Definition at line 981 of file place_qpsolver.c.

{
  int i, j;
  int pr, pw;
  qps_float_t bk;
  int tk;
 
#if defined(QPS_PRECON)
  int c;
  qps_float_t t;
#endif
 
#if defined(QPS_HOIST)
  int k;
  int st;
  int m1, m2;
#endif
 
  if (p->max_enable) {
    p->priv_mxl = (qps_float_t *)
    malloc(4 * p->num_cells * sizeof(qps_float_t));
    assert(p->priv_mxl);
    p->priv_mxh = p->priv_mxl + p->num_cells;
    p->priv_myl = p->priv_mxl + 2 * p->num_cells;
    p->priv_myh = p->priv_mxl + 3 * p->num_cells;
    for (i = 4 * p->num_cells; i--;) {
      p->priv_mxl[i] = 0.0;
    }
  }
 
  /* flag fixed cells with -1 */
  for (i = p->num_cells; i--;) {
    p->priv_ii[i] = (p->fixed[i]) ? (-1) : (0);
  }
 
  /* read gl and set up dependent variables */
  if (p->cog_num) {
    p->priv_gt = (int *)malloc(p->cog_num * sizeof(int));
    assert(p->priv_gt);
    p->priv_gm = (qps_float_t*)malloc(p->cog_num * sizeof(qps_float_t));
    assert(p->priv_gm);
    pr = 0;
    for (i = 0; i < p->cog_num; i++) {
      tk = -1;
      bk = -1.0;
      pw = pr;
      while ((j = p->cog_list[pr++]) >= 0) {
    if (!p->fixed[j]) {
      /* use largest entry for numerical stability; see Gordian paper */
      if (p->area[j] > bk) {
        tk = j;
        bk = p->area[j];
      }
    }
      }
      assert(bk > 0.0);
      /* dependent variables have index=(-2-COG_constraint) */
      p->priv_ii[tk] = -2 - i;
      p->priv_gt[i] = pw;
      p->priv_gm[i] = bk;
    }
    p->priv_gw = (qps_float_t*)malloc(pr * sizeof(qps_float_t));
    assert(p->priv_gw);
    pr = 0;
    for (i = 0; i < p->cog_num; i++) {
      while ((j = p->cog_list[pr]) >= 0) {
    p->priv_gw[pr] = p->area[j] / p->priv_gm[i];
    pr++;
      }
      p->priv_gw[pr] = -1.0;
      pr++;
    }
  }
 
  /* set up indexes from independent floating cells to variables */
  p->priv_n = 0;
  for (i = p->num_cells; i--;) {
    if (!p->priv_ii[i]) {
      p->priv_ii[i] = 2 * (p->priv_n++);
    }
  }
  p->priv_n *= 2;
 
#if (QPS_DEBUG > 5)
  for (i = 0; i < p->num_cells; i++) {
    fprintf(p->priv_fp, "### ii %d %d\n", i, p->priv_ii[i]);
  }
#endif
 
#if defined(QPS_PRECON)
  p->priv_pcg = (qps_float_t *) malloc(p->num_cells * sizeof(qps_float_t));
  assert(p->priv_pcg);
  p->priv_pcgt = (qps_float_t *) malloc(p->priv_n * sizeof(qps_float_t));
  assert(p->priv_pcgt);
  for (i = p->num_cells; i--;) {
    p->priv_pcg[i] = 0.0;
  }
  pr = 0;
  for (i = 0; i < p->num_cells; i++) {
    while ((c = p->priv_cc[pr]) >= 0) {
      t = p->priv_ct[pr];
      p->priv_pcg[i] += t;
      p->priv_pcg[c] += t;
      pr++;
    }
    pr++;
  }
  pr = 0;
  for (i = 0; i < p->loop_num; i++) {
    t = 2.0 * p->loop_penalty[i];
    while ((c = p->loop_list[pr++]) >= 0) {
      p->priv_pcg[c] += t;
    }
    pr++;
  }
#if (QPS_DEBUG > 6)
  for (i = p->num_cells; i--;) {
    fprintf(p->priv_fp, "### precon %d %.2e\n", i, p->priv_pcg[i]);
  }
#endif
  for (i = p->priv_n; i--;) {
      p->priv_pcgt[i] = 0.0;
  }
  for (i = 0; i < p->num_cells; i++) {
    c = p->priv_ii[i];
    if (c >= 0) {
      t = p->priv_pcg[i];
      p->priv_pcgt[c] += t;
      p->priv_pcgt[c + 1] += t;
    }
#if 0
    else if (c < -1) {
      pr = p->priv_gt[-(c+2)];
      while ((j = p->cog_list[pr++]) >= 0) {
    ji = p->priv_ii[j];
    if (ji >= 0) {
      w = p->area[j] / p->area[i];
      t = w * w * p->priv_pcg[i];
      p->priv_pcgt[ji] += t;
      p->priv_pcgt[ji + 1] += t;
    }
      }
    }
#endif
  }
  for (i = 0; i < p->priv_n; i++) {
    t = p->priv_pcgt[i];
    if (fabs(t) < QPS_PRECON_EPS || fabs(t) > 1.0/QPS_PRECON_EPS) {
      p->priv_pcgt[i] = 1.0;
    }
    else {
      p->priv_pcgt[i] = 1.0 / p->priv_pcgt[i];
    }
  }
#endif
 
  /* allocate variable storage */
  p->priv_cp = (qps_float_t *) malloc(4 * p->priv_n * sizeof(qps_float_t));
  assert(p->priv_cp);
 
  /* temp arrays for cg */
  p->priv_g = p->priv_cp + p->priv_n;
  p->priv_h = p->priv_cp + 2 * p->priv_n;
  p->priv_xi = p->priv_cp + 3 * p->priv_n;
 
  /* set values */
  for (i = p->num_cells; i--;) {
    if (p->priv_ii[i] >= 0) {
      p->priv_cp[p->priv_ii[i]] = p->x[i];
      p->priv_cp[p->priv_ii[i] + 1] = p->y[i];
    }
  }
 
  if (p->loop_num) {
    p->priv_lt = (qps_float_t *) malloc(p->loop_num * sizeof(qps_float_t));
    assert(p->priv_lt);
#if defined(QPS_HOIST)
    pr = 0;
    for (i=p->loop_num; i--;) {
      while (p->loop_list[pr++] >= 0) {
      }
      pr++;
    }
    p->priv_lm = pr;
    p->priv_la = (int *) malloc(pr * sizeof(int));
    assert(p->priv_la);
    pr = 0;
    for (i = 0; i < p->loop_num; i++) {
      j = st = p->loop_list[pr++];
      while ((k = p->loop_list[pr]) >= 0) {
    if (j > k) {
      m1 = k;
      m2 = j;
    }
    else {
      assert(k > j);
      m1 = j;
      m2 = k;
    }
    pw = p->priv_cr[m1];
    while (p->priv_cc[pw] != m2) {
/*      assert(p->priv_cc[pw] >= 0); */
      if (p->priv_cc[pw] < 0) {
        pw = -2;
        break;
      }
      pw++;
    }
    p->priv_la[pr-1] = pw;
    j = k;
    pr++;
      }
      if (j > st) {
    m1 = st;
    m2 = j;
      }
      else {
    assert(st > j);
    m1 = j;
    m2 = st;
      }
      pw = p->priv_cr[m1];
      while (p->priv_cc[pw] != m2) {
/*    assert(p->priv_cc[pw] >= 0); */
    if (p->priv_cc[pw] < 0) {
      pw = -2;
      break;
    }
    pw++;
      }
      p->priv_la[pr-1] = pw;
      p->priv_la[pr] = -1;
      pr++;
    }
#endif /* QPS_HOIST */
  }
 
  do {
    qps_solve_inner(p);
  } while (!p->loop_done || !p->max_done);
 
  /* retrieve values */
  /* qps_settp() should have already been called at this point */
  for (i = p->num_cells; i--;) {
    p->x[i] = p->priv_tp[i * 2];
    p->y[i] = p->priv_tp[i * 2 + 1];
  }
#if (QPS_DEBUG > 5)
  for (i = p->num_cells; i--;) {
    fprintf(p->priv_fp, "### cloc %d %f %f\n", i, p->x[i], p->y[i]);
  }
#endif
 
  free(p->priv_cp);
  if (p->max_enable) {
    free(p->priv_mxl);
  }
  if (p->cog_num) {
    free(p->priv_gt);
    free(p->priv_gm);
    free(p->priv_gw);
  }
  if(p->loop_num) {
    free(p->priv_lt);
#if defined(QPS_HOIST)
    free(p->priv_la);
#endif
  }
 
#if defined(QPS_PRECON)
  free(p->priv_pcg);
  free(p->priv_pcgt);
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function: