aboutsummaryrefslogtreecommitdiffstats
path: root/native
Commit message (Collapse)AuthorAge
* Remove unused field from QPA implementationBjoern Brandenburg2013-08-14
| | | | | | | | | | Silences a Clang++ warning/error: > In file included from src/edf/qpa.cpp:12: > include/edf/qpa.h:7:18: error: private field 'm' is not used [-Werror,-Wunused-private-field] > unsigned int m; > ^ > 1 error generated.
* Implement LP-based OMIP blocking analysisBjoern Brandenburg2013-07-12
|
* Fix broken demand calculationBjoern Brandenburg2013-05-22
| | | | | | | Felipe Cerqueira reported incorrect QPA results. The root cause was a corner case in the demand calculation. This patch fixes the underestimation of demand if time == deadline and adds a test case discovered by Felipe that triggered the bug.
* 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.
* Refactor linprog_solve() into a proper functionBjoern Brandenburg2013-02-12
|
* Disable creation of new variables after creation of the objective functionBjoern Brandenburg2013-02-12
| | | | This can reveal bugs in constraints that accidentally include Ti.
* Switch to CPX (CPLEX C API) as default LP solverBjoern Brandenburg2013-02-12
| | | | Much faster than the alternatives, so use it when available.
* 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
|
* Export the LP-based analysis of the DFLP/DPCPBjoern Brandenburg2013-02-12
| | | | | ...via Swig to Python. The actual Python API will be finalized later.
* 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.
* Allow VarMapper to start at index other than 0Bjoern Brandenburg2013-02-12
| | | | This is in preparation of merged LPs.
* 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.
* Simplify sharedres_types.h with iterator macrosBjoern Brandenburg2013-02-12
| | | | Explicit iterator handling is cumbersome. Hide it when possible.
* Extract sharedres_types.h from sharedres.hBjoern Brandenburg2013-02-12
| | | | | The LP code requires many of the same definitions. Therefore, this patch splits the reusable type definitions into an individual file to facilitate inclusion.
* 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.
* Inform about Python version during build processBjoern Brandenburg2013-01-15
|
* 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.
* Do not disable assertions in non-debug buildsBjoern Brandenburg2012-11-24
| | | | It's better to crash with an assertation than to produce wrong results...
* Cleanup native/ MakefileBjoern Brandenburg2012-11-24
| | | | | | - Normalize line endings. - Introduce DEFS variable to allow user to specify definitions in .config. - Add -Werror to avoid accumulating warnings.
* 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
|
* Fix wrong #endif to silence compiler warningsBjoern Brandenburg2012-11-24
| | | | There should be no symbol after #endif.
* 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.
generated by cgit v1.2.2 (git 2.25.0) at 2025-06-14 13:31:29 -0400