[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Commit-gnuradio] r4038 - gnuradio/branches/developers/jcorgan/hier/gnur
From: |
jcorgan |
Subject: |
[Commit-gnuradio] r4038 - gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime |
Date: |
Tue, 28 Nov 2006 12:10:34 -0700 (MST) |
Author: jcorgan
Date: 2006-11-28 12:10:33 -0700 (Tue, 28 Nov 2006)
New Revision: 4038
Modified:
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
Log:
Work in progress. Able to flatten and partition graph.
Modified:
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
===================================================================
---
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
2006-11-28 06:23:20 UTC (rev 4037)
+++
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.cc
2006-11-28 19:10:33 UTC (rev 4038)
@@ -38,7 +38,8 @@
gr_block_detail::gr_block_detail (unsigned int ninputs, unsigned int noutputs)
: d_ninputs (ninputs), d_noutputs (noutputs),
d_input (ninputs), d_output (noutputs),
- d_done (false)
+ d_done (false),
+ d_color (gr_block_detail::WHITE)
{
s_ncurrently_allocated++;
}
Modified:
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
===================================================================
---
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
2006-11-28 06:23:20 UTC (rev 4037)
+++
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_block_detail.h
2006-11-28 19:10:33 UTC (rev 4038)
@@ -1,19 +1,19 @@
/* -*- c++ -*- */
/*
* Copyright 2004 Free Software Foundation, Inc.
- *
+ *
* This file is part of GNU Radio
- *
+ *
* GNU Radio is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2, or (at your option)
* any later version.
- *
+ *
* GNU Radio is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more detail.
- *
+ *
* You should have received a copy of the GNU General Public License
* along with GNU Radio; see the file COPYING. If not, write to
* the Free Software Foundation, Inc., 51 Franklin Street,
@@ -75,18 +75,26 @@
void produce_each (int how_many_items);
+ /*!
+ * \brief Allow the flowgraph to set for sorting and partitioning
+ */
+ enum vcolor { WHITE, GREY, BLACK };
+ void set_color(vcolor color) { d_color = color; }
+ vcolor color() const { return d_color; }
+
//
----------------------------------------------------------------------------
private:
- unsigned int d_ninputs;
- unsigned int d_noutputs;
+ unsigned int d_ninputs;
+ unsigned int d_noutputs;
std::vector<gr_buffer_reader_sptr> d_input;
- std::vector<gr_buffer_sptr> d_output;
- bool d_done;
-
+ std::vector<gr_buffer_sptr> d_output;
+ bool d_done;
+ vcolor d_color;
+
gr_block_detail (unsigned int ninputs, unsigned int noutputs);
- friend gr_block_detail_sptr
+ friend gr_block_detail_sptr
gr_make_block_detail (unsigned int ninputs, unsigned int noutputs);
};
Modified:
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
===================================================================
---
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
2006-11-28 06:23:20 UTC (rev 4037)
+++
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.cc
2006-11-28 19:10:33 UTC (rev 4038)
@@ -36,7 +36,8 @@
gr_runtime_impl::gr_runtime_impl(gr_hier_block2_sptr top_block) :
d_running(false),
d_top_block(top_block),
-d_sfg(gr_make_simple_flowgraph())
+d_sfg(gr_make_simple_flowgraph()),
+d_graphs()
{
}
@@ -55,9 +56,15 @@
else
d_running = true;
+ d_sfg->d_detail->reset();
d_top_block->d_detail->flatten(d_sfg);
d_sfg->d_detail->validate();
d_sfg->d_detail->setup_connections();
+
+ d_graphs = d_sfg->d_detail->partition();
+ if (GR_RUNTIME_IMPL_DEBUG)
+ std::cout << "Flow graph has " << d_graphs.size()
+ << " sub-graphs." << std::endl;
}
void
Modified:
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
===================================================================
---
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
2006-11-28 06:23:20 UTC (rev 4037)
+++
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_runtime_impl.h
2006-11-28 19:10:33 UTC (rev 4038)
@@ -24,6 +24,7 @@
#define INCLUDED_GR_RUNTIME_IMPL_H
#include <gr_runtime_types.h>
+#include <gr_block.h>
class gr_runtime_impl
{
@@ -31,10 +32,11 @@
gr_runtime_impl(gr_hier_block2_sptr top_block);
friend class gr_runtime;
- bool d_running;
- gr_hier_block2_sptr d_top_block;
- gr_simple_flowgraph_sptr d_sfg;
-
+ bool d_running;
+ gr_hier_block2_sptr d_top_block;
+ gr_simple_flowgraph_sptr d_sfg;
+ std::vector<gr_block_vector_t> d_graphs;
+
void start();
void stop();
void wait();
Modified:
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
===================================================================
---
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
2006-11-28 06:23:20 UTC (rev 4037)
+++
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.cc
2006-11-28 19:10:33 UTC (rev 4038)
@@ -1,19 +1,19 @@
/* -*- c++ -*- */
/*
* Copyright 2006 Free Software Foundation, Inc.
- *
+ *
* This file is part of GNU Radio
- *
+ *
* GNU Radio is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2, or (at your option)
* any later version.
- *
+ *
* GNU Radio is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
- *
+ *
* You should have received a copy of the GNU General Public License
* along with GNU Radio; see the file COPYING. If not, write to
* the Free Software Foundation, Inc., 51 Franklin Street,
@@ -34,8 +34,8 @@
#define GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG 1
-gr_edge_sptr
-gr_make_edge(const std::string &src_name, int src_port,
+gr_edge_sptr
+gr_make_edge(const std::string &src_name, int src_port,
const std::string &dst_name, int dst_port)
{
return gr_edge_sptr(new gr_edge(src_name, src_port, dst_name, dst_port));
@@ -46,7 +46,7 @@
d_dst(dst_name, dst_port)
{
}
-
+
gr_edge::~gr_edge()
{
}
@@ -56,11 +56,19 @@
d_edges()
{
}
-
+
gr_simple_flowgraph_detail::~gr_simple_flowgraph_detail()
{
}
+void
+gr_simple_flowgraph_detail::reset()
+{
+ // Boost shared pointers will deallocate as needed
+ d_edges.clear();
+ d_components.clear();
+}
+
gr_block_sptr
gr_simple_flowgraph_detail::lookup_block(const std::string &name)
{
@@ -93,7 +101,7 @@
if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
std::cout << "Connecting " << src_name << ":" << src_port << "->"
<< dst_name << ":" << dst_port << std::endl;
-
+
if (!src_block)
throw std::invalid_argument("unknown src name");
if (!dst_block)
@@ -103,7 +111,7 @@
check_valid_port(dst_block->input_signature(), dst_port);
check_dst_not_used(dst_name, dst_port);
check_type_match(src_block, src_port, dst_block, dst_port);
-
+
d_edges.push_back(gr_make_edge(src_name, src_port, dst_name, dst_port));
}
@@ -153,7 +161,7 @@
used_ports = calc_used_ports(p->first, false); // outputs
noutputs = used_ports.size();
check_contiguity(p->second, used_ports, false); // outputs
-
+
if (!(p->second->check_topology(ninputs, noutputs)))
throw std::runtime_error("check topology failed");
}
@@ -168,7 +176,7 @@
std::vector<int> tmp, result;
std::insert_iterator<std::vector<int> > inserter(result, result.begin());
-
+
gr_edge_vector_t edges = calc_connections(name, check_inputs);
for (gr_edge_viter_t p = edges.begin(); p != edges.end(); p++) {
@@ -177,14 +185,14 @@
else
tmp.push_back((*p)->src_port());
}
-
+
// remove duplicates
std::sort(tmp.begin(), tmp.end());
std::unique_copy(tmp.begin(), tmp.end(), inserter);
if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
std::cout << result.size() << std::endl;
-
+
return result;
}
@@ -216,12 +224,12 @@
std::cout << "Checking " << (check_inputs ? "input " : "output ")
<< "contiguity...";
- gr_io_signature_sptr sig =
+ gr_io_signature_sptr sig =
check_inputs ? block->input_signature() : block->output_signature();
int nports = used_ports.size();
int min_ports = sig->min_streams();
-
+
if (nports == 0) {
if (min_ports == 0) {
if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
@@ -230,9 +238,9 @@
}
else {
if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
- std::cout << "needs " << min_ports << ", only has "
+ std::cout << "needs " << min_ports << ", only has "
<< nports << std::endl;
-
+
throw std::runtime_error("insufficient ports");
}
}
@@ -277,7 +285,7 @@
// Get its detail and edges that feed into it
gr_block_detail_sptr detail = p->second->detail();
gr_edge_vector_t in_edges = calc_upstream_edges(p->first);
-
+
// For each edge that feeds into it
for (gr_edge_viter_t e = in_edges.begin(); e != in_edges.end(); e++) {
// Set the input buffer on the destination port to the output
@@ -290,7 +298,7 @@
if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
std::cout << "Setting input on " << (*e)->dst_name()
<< ":" << dst_port << std::endl;
-
+
detail->set_input(dst_port, gr_buffer_add_reader(src_buffer,
p->second->history()-1));
}
}
@@ -302,7 +310,7 @@
gr_block_sptr block = lookup_block(name);
int item_size = block->output_signature()->sizeof_stream_item(port);
int nitems = s_fixed_buffer_size/item_size;
-
+
// Make sure there are at least twice the output_multiple no. of items
if (nitems < 2*block->output_multiple()) // Note: this means
output_multiple()
nitems = 2*block->output_multiple(); // can't be changed by block
dynamically
@@ -316,11 +324,11 @@
int history = (*p)->history();
nitems = std::max(nitems, 2*(decimation*multiple+history));
}
-
+
if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
std::cout << "Allocating buffer for port " << port << " with "
<< nitems << " items of size " << item_size << std::endl;
-
+
return gr_make_buffer(nitems, item_size);
}
@@ -329,11 +337,11 @@
{
gr_block_vector_t tmp, result;
std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
-
+
for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
if ((*p)->src_name() == name && (*p)->src_port() == port)
tmp.push_back(lookup_block((*p)->dst_name()));
-
+
// Remove duplicates
sort(tmp.begin(), tmp.end());
unique_copy(tmp.begin(), tmp.end(), inserter);
@@ -344,10 +352,122 @@
gr_simple_flowgraph_detail::calc_upstream_edges(const std::string &name)
{
gr_edge_vector_t result;
-
+
for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++)
if ((*p)->dst_name() == name)
result.push_back(*p);
return result; // Assume no duplicates
}
+
+gr_block_vector_t
+gr_simple_flowgraph_detail::calc_used_blocks()
+{
+ std::vector<std::string> tmp, tmp_unique;
+ std::insert_iterator<std::vector<std::string> > inserter(tmp_unique,
tmp_unique.begin());
+ gr_block_vector_t result;
+
+ for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+ tmp.push_back((*p)->src_name());
+ tmp.push_back((*p)->dst_name());
+ }
+
+ sort(tmp.begin(), tmp.end());
+ unique_copy(tmp.begin(), tmp.end(), inserter);
+
+ for (std::vector<std::string>::iterator p = tmp_unique.begin();
+ p != tmp_unique.end(); p++)
+ result.push_back(lookup_block(*p));
+
+ if (GR_SIMPLE_FLOWGRAPH_DETAIL_DEBUG)
+ std::cout << "Flowgraph uses " << result.size()
+ << " distinct blocks." << std::endl;
+
+ return result;
+}
+
+std::vector<gr_block_vector_t>
+gr_simple_flowgraph_detail::partition()
+{
+ std::vector<gr_block_vector_t> result;
+ gr_block_vector_t blocks = calc_used_blocks();
+ gr_block_vector_t graph;
+
+ while (blocks.size() > 0) {
+ graph = calc_reachable_blocks(blocks[0], blocks);
+ assert(graph.size());
+ result.push_back(topological_sort(graph));
+
+ for (gr_block_viter_t p = graph.begin(); p != graph.end(); p++)
+ blocks.erase(find(blocks.begin(), blocks.end(), *p));
+ }
+
+ return result;
+}
+
+gr_block_vector_t
+gr_simple_flowgraph_detail::calc_reachable_blocks(gr_block_sptr block,
gr_block_vector_t &blocks)
+{
+ gr_block_vector_t result;
+
+ // Mark all blocks as unvisited
+ for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+ (*p)->detail()->set_color(gr_block_detail::WHITE);
+
+ // Recursively mark all reachable blocks
+ reachable_dfs_visit(block, blocks);
+
+ // Collect all the blocks that have been visited
+ for (gr_block_viter_t p = blocks.begin(); p != blocks.end(); p++)
+ if ((*p)->detail()->color() == gr_block_detail::BLACK)
+ result.push_back(*p);
+
+ return result;
+}
+
+gr_block_vector_t
+gr_simple_flowgraph_detail::topological_sort(gr_block_vector_t blocks)
+{
+ gr_block_vector_t result;
+
+ // NOP for now
+ result = blocks;
+
+ return result;
+}
+
+// Recursively mark all reachable blocks from given block and block list
+void
+gr_simple_flowgraph_detail::reachable_dfs_visit(gr_block_sptr block,
gr_block_vector_t &blocks)
+{
+ // Mark the current one as visited
+ block->detail()->set_color(gr_block_detail::BLACK);
+
+ // Recurse into adjacent vertices
+ gr_block_vector_t adjacent = calc_adjacent_blocks(block, blocks);
+
+ for (gr_block_viter_t p = adjacent.begin(); p != adjacent.end(); p++)
+ if ((*p)->detail()->color() == gr_block_detail::WHITE)
+ reachable_dfs_visit(*p, blocks);
+}
+
+// Return a list of block adjacent to a given block along any edge
+gr_block_vector_t
+gr_simple_flowgraph_detail::calc_adjacent_blocks(gr_block_sptr block,
gr_block_vector_t &blocks)
+{
+ gr_block_vector_t tmp, result;
+ std::insert_iterator<gr_block_vector_t> inserter(result, result.begin());
+
+ // Find any blocks that are inputs or outputs
+ for (gr_edge_viter_t p = d_edges.begin(); p != d_edges.end(); p++) {
+ if (lookup_block((*p)->src_name()) == block)
+ tmp.push_back(lookup_block((*p)->dst_name()));
+ if (lookup_block((*p)->dst_name()) == block)
+ tmp.push_back(lookup_block((*p)->src_name()));
+ }
+
+ // Remove duplicates
+ sort(tmp.begin(), tmp.end());
+ unique_copy(tmp.begin(), tmp.end(), inserter);
+ return result;
+}
Modified:
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
===================================================================
---
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
2006-11-28 06:23:20 UTC (rev 4037)
+++
gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime/gr_simple_flowgraph_detail.h
2006-11-28 19:10:33 UTC (rev 4038)
@@ -82,6 +82,7 @@
gr_edge_vector_t d_edges;
static const unsigned int s_fixed_buffer_size = GR_FIXED_BUFFER_SIZE;
+ void reset();
void define_component(const std::string &name, gr_block_sptr block);
void connect(const std::string &src, int src_port,
const std::string &dst, int dst_port);
@@ -99,7 +100,13 @@
gr_buffer_sptr allocate_buffer(const std::string &name, int port);
gr_block_vector_t calc_downstream_blocks(const std::string &name, int
port);
gr_edge_vector_t calc_upstream_edges(const std::string &name);
-
+ gr_block_vector_t calc_used_blocks();
+ std::vector<gr_block_vector_t> partition();
+ gr_block_vector_t calc_reachable_blocks(gr_block_sptr block,
gr_block_vector_t &blocks);
+ gr_block_vector_t topological_sort(gr_block_vector_t blocks);
+ void reachable_dfs_visit(gr_block_sptr block, gr_block_vector_t &blocks);
+ gr_block_vector_t calc_adjacent_blocks(gr_block_sptr block,
gr_block_vector_t &blocks);
+
public:
~gr_simple_flowgraph_detail();
};
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Commit-gnuradio] r4038 - gnuradio/branches/developers/jcorgan/hier/gnuradio-core/src/lib/runtime,
jcorgan <=