One year has passed since I wrote the last entry to this
blog, and everything is so different now. We had to adapt to a very complex
situation, and all our teaching had to be done online this academic year. It
was particularly challenging for embedded systems, which in York has always
been taught as lab-centric topic. With no access to the labs, we had to work
hard to achieve the same learning outcomes using design tools and simulators
that could be run by students in their own computers. We had a couple issues,
particularly with creating and deploying virtual machines with pre-installed tools, but given the circumstances everything went well.
Another challenge was this year’s EMBS Design Contest. The
traditional format where students run against the clock to create an ad-hoc
wireless network across the Computer Science building was clearly not possible
this year. After thinking about it for several weeks, I was ready to cancel the
contest when I had an idea that would be suitable for our circumstances. Since
I had added some new material to the part of EMBS that covers platform-based
design and task mapping algorithms/heuristics (as I was forced to reduce the
content on embedded wireless networking due to no access to the labs), I
thought I could explore that type of problem and formulate a challenge that
people could address in a distributed way.
The problem I devised was to map a large application model
(44 tasks, 68 inter-task communication flows) to a multi-core platform based on
a 2D-mesh network-on-chip. The application tasks and communications were
characterised, respectively, by their processor utilisation and network link
utilisation at nominal frequencies for the cores and interconnect. The
objective was to find a mapping, over the smallest 2D-mesh platform and running
at the smallest fraction of the nominal frequencies, but without over-utilising
any processing core or network-on-chip link. This is an NP-hard problem that I’ve addressed in my research (together with several of my post-doc researchers, Master and PhD students),
but using response time analysis instead of utilisation-based tests. In either
case, there are no known optimal algorithms for this problem, only heuristics
that do not guarantee optimality.
Before releasing the problem, I had to make sure it was challenging
enough, and that it had at least one valid solution. To do that, I have created
a valid mapping for a fairly thin application model onto a 4x3 network-on-chip
platform. I then inflated the utilisations of tasks and communications of that
thin model until that mapping was nearly breaking the utilisation bound of the
platform at arbitrary but realistic frequency levels. The inflated application
model was then be the problem I posed to the students (divided in four groups),
and I had a good solution that I knew was valid (my chosen mapping for a 4x3
platform) and certainly achievable by the students with a bit of effort.
Once the challenge was released, I monitored the progress of all
four groups (and had one videoconference session with each group) over the 2.5
days of the contest. Students were not allowed to choose their groups, and each
group had 8-10 members. I’ve noticed that only 2-5 members of each group were
actively working towards a solution to the design challenge. In past years,
when the design contest happened in the lab, it was common to see 2-3 students
taking the lead, but then all other students would engage or at least learn
from the solutions attempted by the group. In the case of remote/online groups
in 2020, that “side-learning” situation (i.e. students learning from students)
did not really work. This could be an undesired consequence of online
groupwork, but could also be related to the covid circumstances, or to the
heavy workload at the end of the teaching term (especially when running the
contest over 2.5 days instead of an intensive lab-based 2h competition).
Nonetheless, the achievements of the groups were laudable. Three
of the four groups provided valid solutions to the problem. Group 4 actually
found my original solution on a 4x3 platform, using a clever constructive
heuristic that clustered together tasks that had high-utilisation communication
flows between then, followed by some manual adjustments to tidy up the mapping.
But the winner of the EMBS 2020 design contest was Group 3, who came up with a valid
mapping for a 5x2 platform, therefore using fewer processors than the solution
found by Group 4 (and myself). Their approach was based on the use of Genetic
Algorithms for task mapping, which was covered in the new lectures and
practical exercises I added to EMBS this year. Remarkable work, based on an
unusual network-on-chip topology, but fulfilling completely the rubric of the
design contest.
As always, we close the blog post with a picture of the winning
group, Group 3. Fittingly for 2020, the picture is a snapshot of a videoconference. The
group members will receive their prize (a snack giftbox each) via post this year.
And for finding my original solution to the challenge, I
decided to award an honourable mention to Group 4 and add their photo as well.
Finally, links to the complete EMBS Design Contest Hall of Fame, with pictures of the top teams from 2019, 2018, 2017, 2016, 2015, 2014, 2012, 2011 and 2010 (in 2013, no group managed to finish the challenge on time).
