Go to the source code of this file.
Functions | |
| void | Greedy_KWayOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode) |
| void | Greedy_KWayCutOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode) |
| void | Greedy_KWayVolOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode) |
| void | Greedy_McKWayCutOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode) |
| void | Greedy_McKWayVolOptimize (ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode) |
| idx_t | IsArticulationNode (idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where, idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk) |
| void | KWayVolUpdate (ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from, idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr, idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker, idx_t *modind) |
Definition in file kwayfm.c.
| void Greedy_KWayOptimize | ( | ctrl_t * | ctrl, | |
| graph_t * | graph, | |||
| idx_t | niter, | |||
| real_t | ffactor, | |||
| idx_t | omode | |||
| ) |
Definition at line 20 of file kwayfm.c.
References gk_errexit(), Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), Greedy_McKWayVolOptimize(), METIS_OBJTYPE_CUT, METIS_OBJTYPE_VOL, graph_t::ncon, and ctrl_t::objtype.
Referenced by RefineKWay().
| void Greedy_KWayCutOptimize | ( | ctrl_t * | ctrl, | |
| graph_t * | graph, | |||
| idx_t | niter, | |||
| real_t | ffactor, | |||
| idx_t | omode | |||
| ) |
K-way partitioning optimization in which the vertices are visited in decreasing ed/sqrt(nnbrs)-id order. Note this is just an approximation, as the ed is often split across different subdomains and the sqrt(nnbrs) is just a crude approximation.
| graph | is the graph that is being refined. | |
| niter | is the number of refinement iterations. | |
| ffactor | is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint. | |
| omode | is the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE |
Definition at line 60 of file kwayfm.c.
References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, ctrl_t::cnbrpool, ComputeCut(), ComputeLoadImbalance(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, cnbr_t::ed, ckrinfo_t::ed, ckrinfo_t::id, ckrinfo_t::inbr, IsArticulationNode(), iwspacemalloc(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, ctrl_t::nads, graph_t::nbnd, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, cnbr_t::pid, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, rpq_t, ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.
Referenced by Greedy_KWayOptimize().
| void Greedy_KWayVolOptimize | ( | ctrl_t * | ctrl, | |
| graph_t * | graph, | |||
| idx_t | niter, | |||
| real_t | ffactor, | |||
| idx_t | omode | |||
| ) |
K-way refinement that minimizes the communication volume. This is a greedy routine and the vertices are visited in decreasing gv order.
| graph | is the graph that is being refined. | |
| niter | is the number of refinement iterations. | |
| ffactor | is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint. |
Definition at line 370 of file kwayfm.c.
References ctrl_t::adids, graph_t::adjncy, adjncy, ctrl_t::adwgts, graph_t::bndind, graph_t::bndptr, ComputeLoadImbalance(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, vnbr_t::gv, vkrinfo_t::gv, vkrinfo_t::inbr, IsArticulationNode(), iwspacemalloc(), KWayVolUpdate(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, graph_t::minvol, ctrl_t::nads, graph_t::nbnd, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, vnbr_t::pid, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::vsize, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.
Referenced by Greedy_KWayOptimize().
| void Greedy_McKWayCutOptimize | ( | ctrl_t * | ctrl, | |
| graph_t * | graph, | |||
| idx_t | niter, | |||
| real_t | ffactor, | |||
| idx_t | omode | |||
| ) |
K-way partitioning optimization in which the vertices are visited in decreasing ed/sqrt(nnbrs)-id order. Note this is just an approximation, as the ed is often split across different subdomains and the sqrt(nnbrs) is just a crude approximation.
| graph | is the graph that is being refined. | |
| niter | is the number of refinement iterations. | |
| ffactor | is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint. | |
| omode | is the type of optimization that will performed among OMODE_REFINE and OMODE_BALANCE |
Definition at line 684 of file kwayfm.c.
References ctrl_t::adids, graph_t::adjncy, adjncy, graph_t::adjwgt, adjwgt, ctrl_t::adwgts, BetterBalanceKWay(), graph_t::bndind, graph_t::bndptr, graph_t::ckrinfo, ctrl_t::cnbrpool, ComputeCut(), ComputeLoadImbalance(), ComputeLoadImbalanceVec(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, cnbr_t::ed, ckrinfo_t::ed, ckrinfo_t::id, ckrinfo_t::inbr, IsArticulationNode(), IsBalanced(), ivecaxpygez(), ivecaxpylez(), iwspacemalloc(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, ctrl_t::nads, graph_t::nbnd, graph_t::ncon, ncon, ckrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, rpq_t, rvecmaxdiff(), rwspacemalloc(), ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.
Referenced by Greedy_KWayOptimize().
| void Greedy_McKWayVolOptimize | ( | ctrl_t * | ctrl, | |
| graph_t * | graph, | |||
| idx_t | niter, | |||
| real_t | ffactor, | |||
| idx_t | omode | |||
| ) |
K-way refinement that minimizes the communication volume. This is a greedy routine and the vertices are visited in decreasing gv order.
| graph | is the graph that is being refined. | |
| niter | is the number of refinement iterations. | |
| ffactor | is the fudge-factor for allowing positive gain moves to violate the max-pwgt constraint. |
Definition at line 1026 of file kwayfm.c.
References ctrl_t::adids, graph_t::adjncy, adjncy, ctrl_t::adwgts, BetterBalanceKWay(), graph_t::bndind, graph_t::bndptr, ComputeLoadImbalance(), ComputeLoadImbalanceVec(), ComputeSubDomainGraph(), ComputeVolume(), ctrl_t::contig, ctrl_t::dbglvl, vnbr_t::gv, vkrinfo_t::gv, vkrinfo_t::inbr, IsArticulationNode(), IsBalanced(), ivecaxpygez(), ivecaxpylez(), iwspacemalloc(), KWayVolUpdate(), PUP::l, METIS_DBG_MOVEINFO, METIS_DBG_REFINE, ctrl_t::minconn, graph_t::mincut, graph_t::minvol, ctrl_t::nads, graph_t::nbnd, graph_t::ncon, ncon, vnbr_t::ned, vkrinfo_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, ctrl_t::nparts, nparts, graph_t::nvtxs, perm, ctrl_t::pijbm, ctrl_t::pvec1, graph_t::pwgts, rvecmaxdiff(), rwspacemalloc(), ctrl_t::tpwgts, graph_t::tvwgt, ctrl_t::ubfactors, UpdateEdgeSubDomainGraph(), graph_t::vkrinfo, ctrl_t::vnbrpool, graph_t::vsize, graph_t::vwgt, vwgt, graph_t::where, where, graph_t::xadj, and xadj.
Referenced by Greedy_KWayOptimize().
| idx_t IsArticulationNode | ( | idx_t | i, | |
| idx_t * | xadj, | |||
| idx_t * | adjncy, | |||
| idx_t * | where, | |||
| idx_t * | bfslvl, | |||
| idx_t * | bfsind, | |||
| idx_t * | bfsmrk | |||
| ) |
This function performs an approximate articulation vertex test. It assumes that the bfslvl, bfsind, and bfsmrk arrays are initialized appropriately.
Definition at line 1361 of file kwayfm.c.
Referenced by Greedy_KWayCutOptimize(), Greedy_KWayVolOptimize(), Greedy_McKWayCutOptimize(), and Greedy_McKWayVolOptimize().
| void KWayVolUpdate | ( | ctrl_t * | ctrl, | |
| graph_t * | graph, | |||
| idx_t | v, | |||
| idx_t | from, | |||
| idx_t | to, | |||
| ipq_t * | queue, | |||
| idx_t * | vstatus, | |||
| idx_t * | r_nupd, | |||
| idx_t * | updptr, | |||
| idx_t * | updind, | |||
| idx_t | bndtype, | |||
| idx_t * | vmarker, | |||
| idx_t * | pmarker, | |||
| idx_t * | modind | |||
| ) |
This function updates the edge and volume gains due to a vertex movement. v from 'from' to 'to'.
| ctrl | is the control structure. | |
| graph | is the graph being partitioned. | |
| v | is the vertex that is moving. | |
| from | is the original partition of v. | |
| to | is the new partition of v. | |
| queue | is the priority queue. If the queue is NULL, no priority-queue related updates are performed. | |
| vstatus | is an array that marks the status of the vertex in terms of the priority queue. If queue is NULL, this parameter is ignored. | |
| r_nqupd | is the number of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored. | |
| updptr | stores the index of each vertex in updind. If queue is NULL, this parameter is ignored. | |
| updind | is the list of vertices that have been inserted/removed from the queue. If queue is NULL, this parameter is ignored. | |
| vmarker | is of size nvtxs and is used internally as a temporary array. On entry and return all of its entries are 0. | |
| pmarker | is of sie nparts and is used internally as a temporary marking array. On entry and return all of its entries are -1. | |
| modind | is an array of size nvtxs and is used to keep track of the list of vertices whose gains need to be updated. |
Definition at line 1460 of file kwayfm.c.
References graph_t::adjncy, adjncy, graph_t::bndind, graph_t::bndptr, vkrinfo_t::gv, vnbr_t::gv, vkrinfo_t::inbr, PUP::l, graph_t::nbnd, vkrinfo_t::ned, vnbr_t::ned, vkrinfo_t::nid, vkrinfo_t::nnbrs, vnbr_t::pid, PUP::u, graph_t::vkrinfo, ctrl_t::vnbrpool, vnbrpoolGetNext(), graph_t::vsize, vsize, graph_t::where, where, graph_t::xadj, and xadj.
Referenced by Greedy_KWayVolOptimize(), Greedy_McKWayVolOptimize(), MoveGroupContigForVol(), and MoveGroupMinConnForVol().
1.5.5