KDP/Filterski procesi
Filterski procesi su tip zadatka iz distribuiranog programiranja iz trećeg bloka nastave i dolaze na distribuiranom delu ispita za SI i RTI.
Jul-1 2025, 3. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Filterska mreža za traženje minimuma niza. Element mreže na svoje ulaze prima dve[sic] niza celih brojeva koja se završavaju sa vrednošću EOS. Element na jednom izlazu treba da generiše vrednost koja odgovara minimalnoj vrednosti iz primljenih nizova, i nakon toga vrednost EOS. Prikazati filtersku mrežu koja najbrže nalazi minimum 11 vrednosti.
Rešenje
Septembar 2023, 3. zadatak
Postavka
Filterski procesi imaju jedan ulaz i jedan izlaz i rade sledeće: primaju pozitivne vrednosti na ulazu i prosleđuju ih na izlaz ako su veće od zapamćenog minimuma procesa. Procesi imaju samo dve lokacije, za sačuvani minimum i za poslednju primljenu vrednost. Kada na ulaz stigne EOS, izbacuju minimalnu vrednost na izlaz a zatim EOS. Napravite protočnu obradu (pipeline) od n procesa koji opadajuće soritaju do n ulaznih pozitivnih vrednosti koje se ubacuju na početak protočne obrade a završavaju se sa EOS.
Rešenje
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
}
out.send(min);
out.send(EOS);
}
Februar 2020, 3. zadatak
Postavka
Filterski procesi imaju jedan ulaz i jedan izlaz. Procesi imaju samo tri lokacije. Napravite protočnu obradu (pipeline) od n ovih filterskih procesa koji pronalaze medijanu: do n ulaznih pozitivnih vrednosti (neparno) koje se ubacuju na početak protočne obrade, a završavaju se sa EOS. Na izlaz protočne obrade se šalje medijana pa EOS.
Rešenje
Pošto je u zadatku rečeno da je dozvoljeno koristiti samo tri lokacije u procesu, jedna će biti odvojena za broj koji pristiže a druge dve za lokalne minimume i maksimume. Pamtiće se minimumi i maksimumi jer je medijana neparnog broja elemenata upravo ona vrednost koja je tačno na sredini liste u sortiranom poretku. Za razliku od drugih rešenja ovakvog tipa zadatka na vikiju, ništa se ne šalje na izlaz osim EOS kad se isti primi jer je sva obrada za medijanu već razrešena unutar petlje.
void process() {
chan<int> in;
chan<int> out;
int input;
int mem[2];
while ((input = in.receive()) != EOS) {
if (mem[0] <= input && input <= mem[1]) {
out.send(input);
} else if (input < mem[0]) {
out.send(mem[0]);
mem[0] = input;
} else if (input > mem[1]) {
out.send(mem[1]);
mem[1] = input;
}
}
out.send(EOS);
}
Februar 2021, 3. zadatak
Postavka
Filterski procesi imaju jedan ulaz i jedan izlaz, i do tri lokacije za primljene brojeva. Napravite protočnu obradu (pipeline) od n ovih filterskih procesa koja sortira pa sabira do 2*n ulaznih realnih brojeva koje se ubacuju na početak protočne obrade, a završavaju se sa EOS. Na izlaz protočne obrade se šalje suma pa EOS.
Rešenje
Kada stigne EOS, ukoliko su se sve ostale vrednosti propagirale kroz mrežu, ove vrednosti će biti sortirane od najveće ka najmanjoj kako se redom bude išlo kroz sadržaj filterskih procesa. U zadatku nije specificirano na koji način treba da se vidi činjenica da se niz sortira, pa je ovo uzeto kao pretpostavka.
void process() {
chan<int> in;
chan<int> out;
int numReceived = 0;
int input;
int mem[2];
while ((input = in.receive()) != EOS) {
if (numReceived < 2) {
mem[numReceived++] = input;
} else {
if (input <= mem[0] && input <= mem[1]) {
out.send(input);
} else if (mem[0] <= input && mem[0] <= mem[1]) {
out.send(mem[0]);
mem[0] = input;
} else {
out.send(mem[1]);
mem[1] = input;
}
}
}
out.send(mem[0] + mem[1]);
out.send(EOS);
}