aboutsummaryrefslogtreecommitdiffstats
path: root/native/src
Commit message (Collapse)AuthorAge
* Implement LP-based OMIP blocking analysisBjoern Brandenburg2013-07-12
|
* Precision fix: user deliberate rounding in LP result conversionBjoern Brandenburg2013-02-12
| | | | | | | Use proper rounding when converting blocking terms to avoid rounding issues. This could cause some (very rare) off-by-one bugs when incorrectly truncating an objective result very close to the next largest integer.
* Add LP-based blocking analysis for FMLP+Bjoern Brandenburg2013-02-12
|
* Add LP-based blocking analysis for MPCPBjoern Brandenburg2013-02-12
|
* Add generic LP support for shared-memory protocolsBjoern Brandenburg2013-02-12
|
* Allow LPs in which not all variables are part of the objective functionBjoern Brandenburg2013-02-12
|
* Add support for dumping LPs to iostreamsBjoern Brandenburg2013-02-12
| | | | Quite handy when debugging LPs...
* C++ LP analysis: add LP debugging helperBjoern Brandenburg2013-02-12
| | | | Dump a LP solution to a stream for inspection.
* Disable creation of new variables after creation of the objective functionBjoern Brandenburg2013-02-12
| | | | This can reveal bugs in constraints that accidentally include Ti.
* Implement CPLEX integration via C APIBjoern Brandenburg2013-02-12
| | | | | | | | Using the plain, old C API seems to be *much* faster. single: lp_dpcp_bounds::cpu_costs: total=19569.9ms last=93.2767ms average=88.9543ms count=220 lp_dflp_bounds::cpu_costs: total=21537.3ms last=102.459ms average=97.8969ms count=220
* Set CPLEX options to improve solving speedBjoern Brandenburg2013-02-12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | With CPLEX 12, we are seeing the following solving speeds. single + Primal + PreDuall=-1: lp_dpcp_bounds::cpu_costs: total=23692.1ms last=403.739ms average=401.561ms count=59 lp_dflp_bounds::cpu_costs: total=27054.6ms last=459.518ms average=458.553ms count=59 single + Primal + PreDual=1: lp_dpcp_bounds::cpu_costs: total=33478.5ms last=404.556ms average=403.355ms count=83 lp_dflp_bounds::cpu_costs: total=38773.8ms last=467.097ms average=467.154ms count=83 single + Primal + DepInd=3: lp_dpcp_bounds::cpu_costs: total=18319.7ms last=419.785ms average=416.356ms count=44 lp_dflp_bounds::cpu_costs: total=21017.1ms last=477.474ms average=477.661ms count=44 single + Primal + DepInd=1: lp_dpcp_bounds::cpu_costs: total=12046.9ms last=419.514ms average=415.411ms count=29 lp_dflp_bounds::cpu_costs: total=13843.3ms last=477.015ms average=477.356ms count=29 single + Primal + PreInd=0: lp_dpcp_bounds::cpu_costs: total=17678.5ms last=445.003ms average=441.964ms count=40 lp_dflp_bounds::cpu_costs: total=17841.8ms last=446.056ms average=446.044ms count=40 single + Sifting: lp_dpcp_bounds::cpu_costs: total=42553.6ms last=657.655ms average=709.227ms count=60 lp_dflp_bounds::cpu_costs: total=50444.8ms last=728.922ms average=840.746ms count=60 single + Barrier: lp_dpcp_bounds::cpu_costs: total=28709.2ms last=453.862ms average=455.701ms count=63 lp_dflp_bounds::cpu_costs: total=43688.5ms last=625.312ms average=693.468ms count=63 single + Barrier + DepInd=1: lp_dpcp_bounds::cpu_costs: total=5358.42ms last=452.804ms average=446.535ms count=12 lp_dflp_bounds::cpu_costs: total=9561.53ms last=808.225ms average=796.794ms count=12 single + Dual: lp_dpcp_bounds::cpu_costs: total=63654.2ms last=419.534ms average=418.778ms count=152 lp_dflp_bounds::cpu_costs: total=72434.2ms last=476.049ms average=476.541ms count=152 single + Dual + PreDual: lp_dpcp_bounds::cpu_costs: total=24125.4ms last=403.458ms average=402.089ms count=60 lp_dflp_bounds::cpu_costs: total=27963.9ms last=465.245ms average=466.065ms count=60 single + Dual + PreDual + DepInd=3: lp_dpcp_bounds::cpu_costs: total=28022.3ms last=419.838ms average=418.243ms count=67 lp_dflp_bounds::cpu_costs: total=32532.4ms last=485.097ms average=485.558ms count=67 single + Dual + DepInd=3: lp_dpcp_bounds::cpu_costs: total=123606ms last=419.05ms average=419.002ms count=295 lp_dflp_bounds::cpu_costs: total=140686ms last=477.03ms average=476.903ms count=295
* Set GLPK options to improve solving speedBjoern Brandenburg2013-02-12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | With GLPK v4.43, we are seeing the following solving speends on wks-50-12 with testmain. single: lp_dpcp_bounds::cpu_costs: total=338281ms last=561.457ms average=560.996ms count=603 lp_dflp_bounds::cpu_costs: total=109988ms last=183.426ms average=182.401ms count=603 single+GLP_DUALP: lp_dpcp_bounds::cpu_costs: total=27461.7ms last=397.327ms average=397.996ms count=69 lp_dflp_bounds::cpu_costs: total=31928.1ms last=461.537ms average=462.726ms count=69 single + GLP_DUALP + GLP_PT_STD: lp_dpcp_bounds::cpu_costs: total=16134.9ms last=404.367ms average=403.373ms count=40 lp_dflp_bounds::cpu_costs: total=18827.3ms last=487.815ms average=470.683ms count=40 single + GLP_PT_STD: lp_dpcp_bounds::cpu_costs: total=28215.7ms last=511.512ms average=503.852ms count=56 lp_dflp_bounds::cpu_costs: total=9944.36ms last=177.432ms average=177.578ms count=56 bsingle + GLP_RT_STD: lp_dpcp_bounds::cpu_costs: total=105168ms last=562.115ms average=559.402ms count=188 lp_dflp_bounds::cpu_costs: total=34179ms last=182.362ms average=181.803ms count=188 single + GLP_RT_STD + GLP_PT_STD: lp_dpcp_bounds::cpu_costs: total=190591ms last=510.497ms average=509.602ms count=374 lp_dflp_bounds::cpu_costs: total=65934.2ms last=176.804ms average=176.295ms count=374 With merged LPs, it's unbearably slow: lp_dpcp_bounds::cpu_costs: total=30727.3ms last=15253.7ms average=10242.4ms count=3 lp_dflp_bounds::cpu_costs: total=6389.68ms last=2128.94ms average=2129.89ms count=3
* Add GLPK IntegrationBjoern Brandenburg2013-02-12
| | | | | Add a bridge to the GLPK library. Availability is auto-discovered by the build system. Most of the code is solver-agnostic.
* Add support for tracking total LP generation / solving costBjoern Brandenburg2013-02-12
| | | | | | Interestingly, this shows that generating huge LPs is not necessarily any faster than creating and solving many small LPs. Further investigation required.
* Add memory leak debug code to testmainBjoern Brandenburg2013-02-12
| | | | | The CPLEX integration likes to leak memory. This loop makes it very obvious.
* Add test code for LP-based DPCP/DFLP analysisBjoern Brandenburg2013-02-12
|
* Add compile-time support for merged LPsBjoern Brandenburg2013-02-12
| | | | | | | | This patch introduces the capability to generate one huge LP for an entire task set, instead of generating many smaller LPs (one for each task). It's not clear yet that this is actually any faster.
* Add DPCP and DFLP linear program generationBjoern Brandenburg2013-02-12
| | | | | These files implement the generation and evaluation of linear programs that bound maximum s-aware pi-blocking under the DPCP and the DFLP.
* Add CPLEX integrationBjoern Brandenburg2013-02-12
| | | | | | | This patch introduces a concrete subclass of Solution that implements the actual solving of linear programs by means of invoking the CPLEX Concert Technology API. The project can still be compiled on systems that do not have CPLEX installed.
* Add simple C++ linear program representationBjoern Brandenburg2013-02-12
| | | | | | | - Constraints are expressed as lists of terms. - Linear programs consist of only equalities and less-than-or-equal constraints. - Solvers hide behind an abstract solution class that can evaluate linear expressions.
* Add unique IDs to TaskInfoBjoern Brandenburg2013-02-12
| | | | | The LP code generates variable IDs based on task identity. It's convenient to keep track of this explicitly.
* Extract hash map hack from rw-task-fair.cppBjoern Brandenburg2013-02-12
| | | | | | | | Hashmaps will be needed by the LP code. Additionally, add definitions for hash maps with uint64_t keys. This is only relevant for legacy C++ libs as used on Mac OS X. On Linux, we use the newer C++ '11 STL implementation.
* Add benchmarking helper classBjoern Brandenburg2013-02-12
| | | | | CPUClock is useful for repeatedly measuring how long some piece of code executes.
* MPCP: accurately track per-processor priority ceilingsBjoern Brandenburg2013-02-12
| | | | | | | | The priority ceilings under the MPCP are defined in a way such that one processor has a slightly lower ceiling. This doesn't really affect the outcome much, but this patch changes the analysis to be exactly as defined for the sake of accuracy.
* MPCP: export gcs response-time boundsBjoern Brandenburg2013-02-12
| | | | | | This will be used by the new LP-based MPCP analysis. Also, report local blocking to Python and add a clarifying comment.
* MPCP: report local and remote blocking even if >response_timeBjoern Brandenburg2013-02-12
| | | | | | To make response times monotonically increasing, it is beneficial to have some estimate even if the response_time assumption has been violated.
* MPCP: we must consider gcs' with equal priority ceilingsBjoern Brandenburg2013-02-12
| | | | gcs' with equal priority ceiling cannot be preempted.
* Move get_priority_ceilings() from DPCP to common codeBjoern Brandenburg2013-02-12
| | | | | The LP-based analysis of the DPCP can reuse this, so make it available globally.
* Improvements to the GEL Piecewise Linear module: support for arbitrary GEL ↵Jeremy Erickson2013-02-04
| | | | schedulers in native code and easy max lateness computation.
* Use utilization cap instead of number of CPUs where applicableJeremy Erickson2012-12-27
|
* Minor bug fixes in the QPA implementationBjoern Brandenburg2012-11-28
| | | | | | | 1) On Linux hosts, limits.h must be included explicitly. 2) Don't try to compute the busy interval if the task system is over-utilized.
* Add QPA EDF uniprocessor testBjoern Brandenburg2012-11-27
| | | | Based on Zhang and Burns (2009), "Schedulability Analysis for Real-Time Systems with EDF Scheduling", IEEE Transactions on Computers, Vol 58, No 9.
* Add bound_demand() to TaskSetBjoern Brandenburg2012-11-27
| | | | This corresponds to h(t) in Zhang and Burns (2009)'s QPA paper.
* Add support for clock_gettimeBjoern Brandenburg2012-11-24
| | | | | | Use the more accurate clock under Linux when available. getrusage() unfortunately only has a resolution of 1/HZ (i.e., one jiffie), which is too coarse-grained in many cases.
* Avoid compiler warnings about unused variablesBjoern Brandenburg2012-11-24
|
* Added arbitrary-precision arithmetic to native moduleJeremy Erickson2012-10-29
|
* Initial GEL Piecewise Linear implementationJeremy Erickson2012-09-25
|
* C++: move spinlock bounds to corresponding implementationsBjoern Brandenburg2012-05-17
| | | | Part of refactoring sharedres.cpp.
* C++: Properly consider priority ceilings in DPCP boundBjoern Brandenburg2012-05-17
| | | | The bound should not reflect requests executed by agents that can be preempted.
* C++: move shared RW locking defs into own fileBjoern Brandenburg2012-05-17
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the task-fair RW locks codeBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the phase-fair RW locks codeBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the C-OMLP-KX codeBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the C-OMLP code into own fileBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the P-OMLP code into own fileBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the G-OMLP and G-FMLP code into own fileBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the FMLP+ code into own fileBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* Move MPPC++: Break out the MPCP code into own fileBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* C++: Break out the DPCP code into own fileBjoern Brandenburg2012-05-16
| | | | Part of refactoring sharedres.cpp.
* Rename time types used in C++ schedulablity analysisBjoern Brandenburg2012-04-11
| | | | | | integral_t == integral time units fractional_t == fractions of integral time units This is hopefully less of an eyesore than mpq_class and mpz_class.
generated by cgit v1.2.2 (git 2.25.0) at 2025-08-23 17:20:37 -0400