Balanced scheduler

[imranashraf]

The uniform scheduler is an upgraded asap scheduler. An asap scheduler schedules each gate as soon as possible, i.e. the first possible cycle after the completion of gates of which it needs the results. By this, in some cycles, especially the first cycle of the circuit, many gates will start in parallel, and in the last cycle, there will only be at most one gate. The uniform scheduler balances the number of gates started in each cycle of the circuit over the circuit, starting from an asap schedule. As a consequence the number of cycles with no or just a few gates, and the number of cycles with a high number of gates will be minimized; the variation is minimized; the uniform scheduler tries to start in each cycle the average number of gates. As a consequence, the gate flow into the system will be more steady and the chances for underflow or overflow of internal buffers will be minimized.

[AdriaanRol]

@imranashraf , silly question as this is probably obvious for you but I was wondering what "balanced" means in this context.

[imranashraf]

@jvansomeren is working on it and i already asked him to add more details to this issue I created for him.

[imranashraf]

@jvansomeren pushed the initial implementation on https://github.com/QE-Lab/OpenQL/tree/uniform-sched branch. @lriesebos can you please check if this is what you required?

[lriesebos]

Tested and reduces deviation in bundle sizes significantly. See for example the first histogram of bundle sizes with ALAP scheduling versus the second histogram with uniform scheduling.

rand_rev_norm_square_root_32_scheduled_scheduled_bundle_sizes.pdf rand_rev_norm_square_root_32_scheduled_scheduled_bundle_sizes.pdf

Although there are situations where the bundle sizes are large at the start right now. See for example the first bundle size envelope graph with ALAP scheduling versus the second with uniform scheduling. The ALAP envelope is what we expect, biased towards the end. The uniform scheduled bundle envelope is very nicely uniform, but has for some reason large bundles around the start.

rand_rev_norm_ising_model_192_scheduled_scheduled_bundle_envelope.pdf rand_rev_norm_ising_model_192_scheduled_scheduled_bundle_envelope.pdf

@jvansomeren , could we take a look to see where this behavior comes from?

[lriesebos]

After further improvements the first version of the uniform scheduler can be considered done. Bundle size deviation is reduced significantly. See for example the first bundle size envelope with ALAP scheduling versus the second with uniform scheduling.

rand_rev_norm_ising_model_192_scheduled_scheduled_bundle_envelope.pdf rand_rev_norm_ising_model_192_scheduled_scheduled_bundle_envelope.pdf

The only problem left is that the first bundle stays very large due to a parallel preparation of almost all qubits. This algorithm can probably not solve that in an elegant way. A solution could be to add an other processing step after the uniform scheduler that aggressively cuts very large bundles in smaller one's at the cost of an increased amount of cycles.

[imranashraf]

left over problem will be the focus of https://github.com/QE-Lab/OpenQL/issues/138, so closing it.

[lriesebos]

We found some undesired behavior in the scheduling of the first bundles. Due to an unknown reason prep operations form a large first bundle while multiple of them are not on the critical path and can therefore be delayed. An example output where this behavior is observed can be found here:

rand_rev_norm_ising_model_32_scheduled_scheduled.qasm.txt

@jvansomeren will look into it.

[lriesebos]

Run new analysis and I do not see any strange behavior. The threshold is still floating around a bit, but I guess this is the performance we can reach. @jvansomeren , could you confirm that or do you still see strange behavior from the graphs? If not, I propose that @imranashraf merges the changes.

graphs_uniform_3.tar.gz

[jvansomeren]

The graphs are according to expectation.

Hans

Op 2 jul. 2018, om 18:14 heeft leon notifications@github.com<mailto:notifications@github.com> het volgende geschreven:

Run new analysis and I do not see any strange behavior. The threshold is still floating around a bit, but I guess this is the performance we can reach. @jvansomerenhttps://github.com/jvansomeren , could you confirm that or do you still see strange behavior from the graphs? If not, I propose that @imranashrafhttps://github.com/imranashraf merges the changes.

graphs_uniform_3.tar.gzhttps://github.com/QE-Lab/OpenQL/files/2155930/graphs_uniform_3.tar.gz

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/QE-Lab/OpenQL/issues/137#issuecomment-401856787, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AQcwtvwl3mW-yom7X1yptE45KDaF0cYIks5uCkbngaJpZM4UY_tm.

[imranashraf]

merged into develop.